On the Complexity of Random Satisfiability Problems with Planted Solutions.
Vitaly FeldmanWill PerkinsSantosh S. VempalaPublished in: SIAM J. Comput. (2018)
Keyphrases
- satisfiability problem
- pspace complete
- stochastic local search algorithms
- random sat
- np complete
- phase transition
- search algorithm
- temporal logic
- sat problem
- search procedures
- graph coloring problems
- solving hard
- optimal solution
- sat instances
- randomly generated
- combinatorial problems
- finite domain
- modal logic
- computational complexity
- coalition logic