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. Felix QW (talk) 19:01, 6 February 2022 (UTC)Reply
- Agreed on all accounts. Caleb Stanford (talk) 01:53, 7 February 2022 (UTC)Reply
The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.
