The Power of Choice for Random Satisfiability
Varsha Dani, Josep Dı́az, Thomas P. Hayes, Cristopher Moore · arXiv (Cornell University) · 2012
We consider Achlioptas processes for k-SAT formulas. We create a semi-random formula with n variables and m clauses, where each clause is a choice, made on-line, between two or more uniformly random clauses. Our goal is to delay the satisfiability/unsatisfiability transition, keeping the formula satisfiable up to densities m/n beyond the satisfiability threshold alpha_k for random k-SAT. We show that three choices suffice to raise the threshold for any k >= 3, and that two choices suffice for all 3 = 3, making the formula unsatisfiable at a density below alpha_k.