The Complexity of Minimal Satisfiability Problems

Lefteris M. Kirousis Phokion G. Kolaitis

Published in: Electron. Colloquium Comput. Complex. (2000)

Keyphrases

satisfiability problem
pspace complete
np complete
temporal logic
phase transition
search algorithm
sat problem
computational complexity
stochastic local search algorithms
stochastic local search
random sat
solving hard
decision problems
model checking
sat instances
randomly generated
search strategy
davis putnam