Premium
A spectral technique for random satisfiable 3CNF formulas
Author(s) -
Flaxman Abraham
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20213
Subject(s) - combinatorics , mathematics , struct , random variable , constant (computer programming) , graph , discrete mathematics , set (abstract data type) , computer science , statistics , programming language
Let I be a random 3CNF formula generated by choosing a truth assignment ϕ for variables x 1 , x n uniformly at random and including every clause with i literals set true by ϕ with probability p i , independently. We show that for any constants 0 ≤ η 2 ,η 3 ≤ 1 there is a constant d min so that for all d ≥ d min a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p 1 = d / n 2 , p 2 = η 2 d / n 2 , and p 3 = η 3 d / n 2 . Appropriately setting the η i 's yields natural distributions on satisfiable 3CNFs, not‐all‐equal‐sat 3CNFs, and exactly‐one‐sat 3CNFs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008