On the Complexity of Random Satisfiability Problems with Planted Solutions.
Vitaly FeldmanWill PerkinsSantosh S. VempalaPublished in: STOC (2015)
Keyphrases
- satisfiability problem
- pspace complete
- random sat
- stochastic local search algorithms
- np complete
- search algorithm
- phase transition
- temporal logic
- graph coloring problems
- search procedures
- computational complexity
- solving hard
- combinatorial problems
- stochastic local search
- sat problem
- randomly generated
- decision problems
- sat instances
- max sat
- finite domain
- davis putnam
- search methods
- cellular automata