Probabilistic satisfiability: algorithms with the presence and absence of a phase transition.
Marcelo FingerGlauber De BonaPublished in: Ann. Math. Artif. Intell. (2015)
Keyphrases
- phase transition
- hard problems
- random instances
- satisfiability problem
- combinatorial problems
- stochastic local search
- random constraint satisfaction problems
- computational complexity
- np complete problems
- data structure
- constraint satisfaction
- np complete
- randomly generated
- sat problem
- hamiltonian cycle
- learning algorithm
- relational learning
- orders of magnitude
- optimization problems