Finding cores of random 2-SAT formulae via Poisson cloning
| dc.creator | Kim, Jeong Han | |
| dc.date | 2008-08-12 | |
| dc.date.accessioned | 2026-07-07T09:56:11Z | |
| dc.date.available | 2026-07-07T09:56:11Z | |
| dc.description | For the random 2-SAT formula $F(n,p)$, let $F_C (n,p)$ be the formula left after the pure literal algorithm applied to $F(n,p)$ stops. Using the recently developed Poisson cloning model together with the cut-off line algorithm (COLA), we completely analyze the structure of $F_{C} (n,p)$. In particular, it is shown that, for $\gl:= p(2n-1) = 1+\gs $ with $\gs\gg n^{-1/3}$, the core of $F(n,p)$ has $\thl^2 n +O((\thl n)^{1/2})$ variables and $\thl^2 \gl n+O((\thl n))^{1/2}$ clauses, with high probability, where $\thl$ is the larger solution of the equation $þ- (1-e^{-\thl \gl})=0$. We also estimate the probability of $F(n,p)$ being satisfiable to obtain $$ \pr[ F_2(n, \sfrac{\gl}{2n-1}) is satisfiable ] = \caseth{1-\frac{1+o(1)}{16\gs^3 n}}{if $\gl= 1-\gs$ with $\gs\gg n^{-1/3}$}{}{}{e^{-Θ(\gs^3n)}}{if $\gl=1+\gs$ with $\gs\gg n^{-1/3}$,} $$ where $o(1)$ goes to 0 as $\gs$ goes to 0. This improves the bounds of Bollobás et al. \cite{BBCKW}. | |
| dc.identifier | https://arxiv.org/abs/0808.1599 | |
| dc.identifier | http://arxiv.org/abs/0808.1599 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/166891 | |
| dc.subject | Combinatorics | |
| dc.subject | Computational Complexity | |
| dc.subject | Probability | |
| dc.subject | 05C80 | |
| dc.title | Finding cores of random 2-SAT formulae via Poisson cloning | |
| dc.type | text |