Name
Abstract | ||
|---|---|---|
Let (C
1,C′1),(C
2,C′2),...,(C
m
,C′
m
) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all
4\binomn24\binom{n}{2} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at
each step must be made on-line, without backtracking, but may depend on the clauses chosen previously. We show that there
exists an on-line choice algorithm in the above process which results whp{\emph{whp}} in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)1/4. This contrasts with the well-known fact that a random m-clause formula constructed without the choice of two clauses at each step is unsatisfiable whp{\emph{whp}} whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random
structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes
in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition
to the on-line setting above, we also consider an off-line version in which all m clause-pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For
the off-line setting, we show that the two-choice satisfiability threshold for k-SAT for any fixed k coincides with the standard satisfiability threshold for random 2k-SAT.
|
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-15369-3_53 | Random Structures and Algorithms |
Keywords | Field | DocType |
random graph,random m-clause formula,classical satisfiability threshold,delaying satisfiability,choice process,standard satisfiability threshold,two-choice satisfiability threshold,online choice algorithm,choice algorithm,achlioptas process,random structure,hamilton cycle,probability distribution,difference set,giant component,satisfiability | Discrete mathematics,Combinatorics,Random graph,Existential quantification,Hamiltonian path,Satisfiability,Ordered pair,Giant component,Probability distribution,Backtracking,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 2 | 1042-9832 |
ISBN | Citations | PageRank |
3-642-15368-2 | 2 | 0.38 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alistair Sinclair | 1 | 1506 | 308.40 |
| Dan Vilenchik | 2 | 143 | 13.36 |