Content deleted Content added
m Stub uprated to Start using AWB |
→Merge: new section |
||
Line 6:
Does anyone know how different [[modal logic]]s can be used to describe complexity classes? Traversal of Kripke structures etc. I know the complexities of showing satisfiability in different modal logics; how does that relate to classes of languages expressible in those logics? --[[User:Spug|Spug]] ([[User talk:Spug|talk]]) 14:05, 8 March 2010 (UTC)
== Merge ==
The current coverage of descriptive complexity is quite unsatisfactory. We have what should be the parent article, [[Descriptive complexity theory]], but which really is a stubby list of characterisations of complexity classes. Then we have three pages giving more detailed description of these characterisations, [[FO (complexity)]], [[SO (complexity)]] and [[HO (complexity)]]. The main context is provided at [[FO (complexity)]] rather than here, and [[SO (complexity)]] and [[HO (complexity)]] make little sense without that context.
Most problematically, however, none of the descriptions adequately distinguish between the classes of structures on which a given characterisation holds. For instance, [[Fagin's theorem]] (ESO = NP) holds on all classes of finite structures, while the Immermann-Vardi Theorem (FO(LFP) = P) holds only for ordered structures, and Grädel's theorem (Second-order Horn logic = P) only holds in the presence of a successor relation.
In my opinion, a much better organisation would be to order the characterisations by the complexity classes they are representing, and by the classes of structures on which they are representing them.
The first step would be to merge the existing articles into [[Descriptive complexity theory]], and then we could take it from there. [[User:Felix QW|Felix QW]] ([[User talk:Felix QW|talk]]) 19:01, 6 February 2022 (UTC)
| |||