Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > 0-1 LAWS:
Reports tagged with 0-1 Laws:
TR09-033 | 16th April 2009
Phokion G. Kolaitis, Swastik Kopparty

#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

ISSN 1433-8092 | Imprint