OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 13, Issue 2, April 2003: pp. 261-271
On the Complexity of the First-order Random Theory
Wafik Boulos Lotfallah1
1Department of Engineering Mathematics and Physics, Faculty of Engineering, Cairo University, Egypt. E-mail: email@example.com
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 [ge] 2 be the arity of the vocabulary, he obtained the upper bounds: T [isin] DSPACE ((n/logn)dlogn), and PrT [isin] 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 ([forall]y|x)[psgr](x, y) and ([exist]y|x)[psgr](x, y), which are semantically equivalent to ([forall]y)((y) [ne] x1 [and] ‥ [and] y [ne] xk) [rarr] [psgr](x, y)) and ([exist]y)(y [ne] x1 [and] ‥ [and] y [ne] xk [and] [psgr](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 [isin] DSPACE(n), and PrTx [isin] 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.
Keywords: Random theory; 0-1 laws; pspace-complete; quantified Boolean formula
Table of Contents
Full-Text PDF (119 KB)