DagSemProc.09441.5.pdf
- Filesize: 250 kB
- 12 pages
Document
The complexity of positive first-order logic without equality II: The four-element case
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9441
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-01-07
Cite AsGet BibTex
Barnaby Martin and Jos Martin. The complexity of positive first-order logic without equality II: The four-element case. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09441.5
https://doi.org/10.4230/DagSemProc.09441.5
Abstract
We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over fixed, finite structures B. This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(B). Extending the algebraic methods of a previous paper, we derive a complete complexity classification for these problems as B ranges over structures of domain size 4. Specifically, each problem is either in Logspace, is NP-complete, is co-NP-complete or is Pspace-complete.
Keywords
- Quantified constraints
- Galois connection
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads