Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract).

Dimitris Achlioptas

Published in: STOC (2000)

Keyphrases

extended abstract
lower bound
random sat
upper bound
max sat
branch and bound algorithm
random constraint satisfaction problems
branch and bound
phase transition
random sat instances
optimal solution
objective function
random instances
satisfiability problem
special case
computational complexity
sat problem
np hard