TY - JOUR

T1 - The complexity of random ordered structures

AU - Spencer, Joel H.

AU - St. John, Katherine

N1 - Funding Information:
1 We thank the referees for their helpful comments. The second author gratefully acknowledges support from NSF ITR 01-21651 and MRI 02-15942 and the hospitality of the Centre de Recerca Matemàtica, Barcelona, Spain. 2 Email: spencer@cs.nyu.edu 3 Email: stjohn@lehman.cuny.edu

PY - 2006/1/6

Y1 - 2006/1/6

N2 - We show that for random bit strings, Up(n), with probability, p=12, the first-order quantifier depth D(Up(n)) needed to distinguish non-isomorphic structures is Θ(lglgn), with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p(n) with edge probabiltiy p=12, D(G≤,p(n))=Θ(log*n), contrasting with the results of random (non-ordered) graphs, Gp(n), by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? (2005), to appear in Random Structures and Algorithms] of D(Gp(n))=log1/pn+O(lglgn).

AB - We show that for random bit strings, Up(n), with probability, p=12, the first-order quantifier depth D(Up(n)) needed to distinguish non-isomorphic structures is Θ(lglgn), with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p(n) with edge probabiltiy p=12, D(G≤,p(n))=Θ(log*n), contrasting with the results of random (non-ordered) graphs, Gp(n), by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? (2005), to appear in Random Structures and Algorithms] of D(Gp(n))=log1/pn+O(lglgn).

KW - Ehrenfeucht-Fraisse games

KW - First order logic

KW - Random bit strings

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=29444444407&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=29444444407&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2005.05.030

DO - 10.1016/j.entcs.2005.05.030

M3 - Article

AN - SCOPUS:29444444407

VL - 143

SP - 197

EP - 206

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

IS - SPEC. ISS.

ER -