Content deleted Content added
→Merge: agree |
→Merge: Closed merge discussion. |
||
Line 8:
== Merge ==
{{discussion top|1= '''Merge''' since there was nothing but support for more than a week.}}
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.
Line 16:
: Agreed on all accounts. [[User:Caleb Stanford|Caleb Stanford]] ([[User talk:Caleb Stanford|talk]]) 01:53, 7 February 2022 (UTC)
{{discussion bottom}}
| |||