Random 3-SAT: The Plot Thickens.
Cristian CoarfaDemetrios D. DemopoulosAlfonso San Miguel AguirreDevika SubramanianMoshe Y. VardiPublished in: CP (2000)
Keyphrases
- random sat
- phase transition
- satisfiability problem
- sat problem
- random sat instances
- random constraint satisfaction problems
- boolean satisfiability
- max sat
- davis putnam
- constraint satisfaction
- np complete
- stochastic local search
- sat solvers
- temporal logic
- combinatorial problems
- randomly generated
- graph coloring
- decision problems
- expressive power
- constraint satisfaction problems
- lower bound