What makes a phase transition? Analysis of the random satisfiability problem
Katharina Anna ZweigGergely PallaTamás VicsekPublished in: CoRR (2010)
Keyphrases
- phase transition
- satisfiability problem
- np complete
- random instances
- randomly generated
- sat problem
- constraint satisfaction
- random constraint satisfaction problems
- search algorithm
- sat instances
- temporal logic
- combinatorial problems
- random graphs
- stochastic local search
- random sat
- hard problems
- cellular automata
- stochastic local search algorithms
- easy hard easy pattern