A Complexity Index for Satisfiability Problems.

Endre Boros Yves Crama Peter L. Hammer Michael E. Saks

Published in: SIAM J. Comput. (1994)

Keyphrases

satisfiability problem
pspace complete
np complete
search algorithm
phase transition
computational complexity
temporal logic
index structure
sat problem
solving hard
random sat
lower bound
special case
np hard
orders of magnitude
decision problems