The Complexity of Positive First-Order Logic without Equality
2012
We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B . This may be seen as a natural generalisation of the nonuniform quantified constraint satisfaction problem QCSP( B ). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterizes definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as B ranges over structures of size at most three. Specifically, each problem either is in L, is NP-complete, is co-NP-complete, or is Pspace-complete.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
8
Citations
NaN
KQI