Delaying Satisfiability for Random 2SAT.

Alistair Sinclair Dan Vilenchik

Published in: APPROX-RANDOM (2010)

Keyphrases

random sat
phase transition
satisfiability problem
sat problem
max sat
random constraint satisfaction problems

np complete
constraint satisfaction
boolean satisfiability
random sat instances
constraint satisfaction problems
search algorithm

stochastic local search
davis putnam
temporal logic
sat solvers
sat instances

propositional satisfiability
combinatorial problems
special case
graph coloring
optimal solution