OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 13, Issue 2, April 2003: pp. 261271
On the Complexity of the Firstorder Random Theory
Wafik Boulos Lotfallah^{1}
^{1}Department of Engineering Mathematics and Physics, Faculty of Engineering, Cairo University, Egypt. Email: lotfalla@math.wisc.edu
In a finite relational vocabulary, the firstorder random theory T is the theory of all firstorder 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)^{d}logn), 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 PSPACEcomplete. He further conjectured that the complexity of T strictly increases with the arity d.
In this paper we consider the random theory in firstorder logic with the exclusive quantifiers ([forall]yx)[psgr](x, y) and ([exist]yx)[psgr](x, y), which are semantically equivalent to ([forall]y)((y) [ne] x_{1} [and] ‥ [and] y [ne] x_{k}) [rarr] [psgr](x, y)) and ([exist]y)(y [ne] x_{1} [and] ‥ [and] y [ne] x_{k} [and] [psgr](x, y)) respectively.
Letting T^{x} be the firstorder random theory with exclusive quantifiers and PrT^{x} be the prenex sentences of T^{x}, we show that both T^{x} and PrT^{x} are PSPACEcomplete, and obtain the upper bounds: T^{x} [isin] DSPACE(n), and PrT^{x} [isin] DSPACE(n/logn). We also show that the complexities of T^{x} and PrT^{x} do not depend on the arity d, refuting Grandjean's conjecture when the firstorder quantifiers are exclusive.
This is done by discovering a tight connection between the theory T^{x} (PrT^{x}) on one hand and the theory QBF (PrQBF) of (prenex) quantified Boolean formulas on the other.
Keywords: Random theory; 01 laws; pspacecomplete; quantified Boolean formula
Table of Contents
FullText PDF (119 KB)
