Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition.
Marcelo FingerGlauber De BonaPublished in: IJCAI (2011)
Keyphrases
- phase transition
- satisfiability problem
- random instances
- hard problems
- np complete problems
- combinatorial problems
- stochastic local search
- np complete
- orders of magnitude
- constraint satisfaction
- learning algorithm
- computational complexity
- data structure
- graph coloring
- random graphs
- randomly generated
- sat problem
- propositional logic
- average degree