Speaker
Prof.
Dmitris Achlioptas
(CTI)
Description
We consider random CNF formulas consisting of 2- and
3-clauses, also known as the random (2+p)-SAT model.
Such mixtures arise naturally in the execution of
satisfiability algorithms on random 3-CNF formulas and
their properties are closely connected to algorithmic
performance. It is known that such mixtures are
satisfiable as long as r_2 < 1 and r_3 < 2/3, where r_k is
the ratio of k-clauses to variables. It has been
conjectured that this is tight, i.e., that for every r_3 >
2/3, there exists r_2 < 1, such that the mixture is with
high probability unsatisfiable. If true, the conjecture
implies that the running time of many natural algorithms
goes from linear to exponential around a critical,
algorithm-specific density. We prove the statement of
the conjecture with 2/3 replaced by 1, improving upon
the previous bound requiring r_3 = 2.28… The proof is
via the interpolation method of statistical physics applied
to the ground state energy of the model. Our result
implies that many well-known satisfiability algorithms
require exponential time on random 3-CNF formulas with
density in the provably satisfiable regime.
Joint work with Ricardo Menchaca-Mendez.
Joint work with Ricardo Menchaca-Mendez.
Author
Prof.
Dmitris Achlioptas
(CTI)
