The complexity of minimal satisfiability problems.

Lefteris M. Kirousis Phokion G. Kolaitis

Published in: Inf. Comput. (2003)

Keyphrases

satisfiability problem
pspace complete
np complete
phase transition
search algorithm
temporal logic
sat problem
stochastic local search algorithms
solving hard
stochastic local search
random sat
constraint satisfaction problems
utility function
max sat
sat instances