A Complexity Index for Satisfiability Problems.
Endre BorosYves CramaPeter L. HammerMichael E. SaksPublished in: IPCO (1992)
Keyphrases
- satisfiability problem
- pspace complete
- np complete
- search algorithm
- phase transition
- sat problem
- stochastic local search
- temporal logic
- random sat
- solving hard
- davis putnam
- stochastic local search algorithms
- computational complexity
- description logics
- state space
- heuristic search
- optimal solution
- mazurkiewicz traces