Finding cores of random 2-SAT formulae via Poisson cloning

Details Finding cores of random 2-SAT formulae via Poisson cloning Finding cores of random 2-SAT formulae via Poisson cloning

2008-08-12

arxiv.org/abs/0808.1599v1

Mathematics

Combinatorics

Scientific paper

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 $\th- (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^{-\Theta(\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\'as et al. \cite{BBCKW}.

Affiliated with

Also associated with

No associations

Rating

Finding cores of random 2-SAT formulae via Poisson cloning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding cores of random 2-SAT formulae via Poisson cloning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding cores of random 2-SAT formulae via Poisson cloning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-202550