Speaker:

Dimitris Achlioptas

Title:

Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas

Abstract:

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.