Title:
The Power of Choice for Random Satisfiability
Author(s):
Varsha Dani, Josep Diaz, Thomas Hayes, Cristopher Moore
Paper #:
13-05-015
Date:
May 7, 2013
Abstract:
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 <= k <= 25. We also show that two choices suffice to lower the threshold for all k >= 3, making the formula unsatisfiable at a density below alpha_k.
Facebook
Twitter
LinkedIn
Email Newsletter
SFI News Feed
Google+
YouTube
iTunes U