On the Complexity of Random Satisfiability Problems with Planted Solutions.
Vitaly FeldmanWill PerkinsSantosh S. VempalaPublished in: CoRR (2013)
Keyphrases
- satisfiability problem
- pspace complete
- stochastic local search algorithms
- np complete
- random sat
- search algorithm
- temporal logic
- search procedures
- graph coloring problems
- phase transition
- randomly generated
- max sat
- sat problem
- search methods
- stochastic local search
- constraint satisfaction problems
- model checking
- solving hard
- upper bound
- computational complexity