A Tetrachotomy for Positive First-Order Logic without Equality
Florent Madelaine, Barnaby D. Martin · 2011
We classify completely the complexity of evaluating positive equality-free sentences of first-order logic over a fixed, finite structure D. This problem may be seen as a natural generalisation of the quantified constraint satisfaction problem QCSP(D). We obtain a tetrachotomy for arbitrary finite structures: each problem is either in L, is NP-complete, is co-NP-complete or is P space-complete. Moreover, its complexity is characterised algebraically in terms of the presence or absence of specific surjective hyper-endomorphisms, and, logically, in terms of relativisation properties with respect to positive equality-free sentences. We prove that the meta-problem, to establish for a specific D into which of the four classes the related problem lies, is NP-hard.