descriptive_complexity (453B)
1 # Descriptive complexity 2 3 Less active nowadays: https://eccc.weizmann.ac.il//report/2011/151/ 4 5 - Abiteboul, Hull, Vianu theorem https://en.wikipedia.org/wiki/Abiteboul-Vianu_theorem 6 - [open_problem]: finding a logic that captures [ptime] 7 - [description_logics_descriptive_complexity] 8 - [immerman_vardi_theorem] : [first_order] with [least_fixpoint], or [datalog], is [ptime] on ordered structures (cf [order_invariance]) 9 10 Up: [computational_complexity]