Phase transitions of PP-complete satisfiability problems.
Delbert D. BaileyVíctor DalmauPhokion G. KolaitisPublished in: Discret. Appl. Math. (2007)
Keyphrases
- phase transition
- satisfiability problem
- pspace complete
- np complete
- constraint satisfaction
- randomly generated
- sat instances
- graph coloring
- hard problems
- sat problem
- search algorithm
- temporal logic
- combinatorial problems
- np complete problems
- random instances
- stochastic local search
- davis putnam
- random sat
- random constraint satisfaction problems
- random graphs
- propositional satisfiability
- conjunctive normal form
- orders of magnitude
- constraint satisfaction problems
- evolutionary algorithm