2+p-SAT: Relation of typical-case complexity to the nature of the phase transition.
Rémi MonassonRiccardo ZecchinaScott KirkpatrickBart SelmanLidror TroyanskyPublished in: Random Struct. Algorithms (1999)
Keyphrases
- phase transition
- satisfiability problem
- random sat
- sat problem
- constraint satisfaction
- np complete
- np complete problems
- hard problems
- stochastic local search
- combinatorial problems
- randomly generated
- graph coloring
- average degree
- random instances
- hamiltonian cycle
- boolean satisfiability
- random constraint satisfaction problems
- random graphs
- sat instances
- relational learning
- computational complexity
- davis putnam
- decision problems
- heuristic search
- orders of magnitude