The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
Eric AllenderMichael BaulandNeil ImmermanHenning SchnoorHeribert VollmerPublished in: MFCS (2005)
Keyphrases
- satisfiability problem
- pspace complete
- np complete
- phase transition
- sat problem
- temporal logic
- search algorithm
- computational complexity
- random sat
- stochastic local search
- stochastic local search algorithms
- solving hard
- davis putnam
- decision problems
- max sat
- model checking
- simulated annealing
- mazurkiewicz traces
- combinatorial optimization
- search space