On the Complexity of the First-order Random Theory
Wafik Boulos Lotfallah · Journal of Logic and Computation · 2003
In a finite relational vocabulary, the first‐order random theory T is the theory of all first‐order sentences that are almost everywhere true, i.e. for each such sentence, the fraction of the finite models of size n satisfying the sentence asymptotically tends to 0 or 1 as n tends to infinity. Grandjean studied the computational complexity of the theory T. Letting d ≥ 2 be the arity of the vocabulary, he obtained the upper bounds: T ∈ DSPACE ((n/logn)dlogn), and PrT ∈ DSPACE((n/logn)d), where PrT denotes the set of prenex sentences of T. Also, since T embodies the theory of equality on infinite domains, he deduced that T is PSPACE‐complete. He further conjectured that the complexity of T strictly increases with the arity d. In this paper we consider the random theory in first‐order logic with the exclusive quantifiers (∀y|x)ψ(x, y) and (∃y|x)ψ(x, y), which are semantically equivalent to (∀y)((y) ≠ x1 ∧ ‥ ∧ y ≠ xk) → ψ(x, y)) and (∃y)(y ≠ x1 ∧ ‥ ∧ y ≠ xk ∧ ψ(x, y)) respectively. Letting Tx be the first‐order random theory with exclusive quantifiers and PrTx be the prenex sentences of Tx, we show that both Tx and PrTx are PSPACE‐complete, and obtain the upper bounds: Tx ∈ DSPACE(n), and PrTx ∈ DSPACE(n/logn). We also show that the complexities of Tx and PrTx do not depend on the arity d, refuting Grandjean's conjecture when the first‐order quantifiers are exclusive. This is done by discovering a tight connection between the theory Tx (PrTx) on one hand and the theory QBF (PrQBF) of (prenex) quantified Boolean formulas on the other.