Talk:Descriptive complexity theory

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

Computer science Start‑class Low‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

Low

This article has been rated as Low-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Modal logic

Does anyone know how different modal logics 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? --Spug (talk) 14:05, 8 March 2010 (UTC)[reply]

Merge

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

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.

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.