Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue

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: lotfalla@math.wisc.edu

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)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement