Skip Navigation

Journal of Logic and Computation 2003 13(2):261-271; doi:10.1093/logcom/13.2.261
© 2003 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Lotfallah, W. B.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Article

On the Complexity of the First-order Random Theory

Wafik Boulos Lotfallah1

1 Department of Engineering Mathematics and Physics, Faculty of Engineering, Cairo University, Egypt. E-mail: lotfalla{at}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 ≥ 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 ({forall}y|x){psi}(x, y) and (y|x){psi}(x, y), which are semantically equivalent to ({forall}y)((y) != x1 {wedge} .. {wedge} y != xk) -> {psi}(x, y)) and (y)(y != x1 {wedge} .. {wedge} y != xk {wedge} {psi}(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.

Keywords: Random theory; 0-1 laws; pspace-complete; quantified Boolean formula

Received 21 September 1999.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.