The Complexity of Random Ordered Structures | Zendy

Joel Spencer | Zendy; Katherine St. John | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Complexity of Random Ordered Structures

Author(s) -

Joel Spencer,

Katherine St. John

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.05.030

Subject(s) - random graph , combinatorics , mathematics , quantifier (linguistics) , discrete mathematics , order (exchange) , graph , computer science , finance , artificial intelligence , economics

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)

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research