Simplest random K-satisfiability problem
Federico Ricci-TersenghiMartin WeigtRiccardo ZecchinaPublished in: CoRR (2000)
Keyphrases
- satisfiability problem
- np complete
- temporal logic
- phase transition
- search algorithm
- sat problem
- random sat
- solving hard
- randomly generated
- stochastic local search algorithms
- sat instances
- max sat
- stochastic local search
- random instances
- model checking
- conjunctive normal form
- weighted max sat
- mazurkiewicz traces
- search strategies
- database
- constraint satisfaction
- simulated annealing
- state space
- special case