Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Piotr BermanMarek KarpinskiAlex D. ScottPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- phase transition
- sat instances
- random instances
- satisfiability problem
- stochastic local search
- sat problem
- randomly generated
- random sat
- np complete
- easy hard easy pattern
- np complete problems
- propositional satisfiability
- solving hard
- sat solvers
- constraint satisfaction
- boolean formula
- continuous functions
- constraint satisfaction problems
- search procedures
- random sat instances
- boolean satisfiability
- max sat
- graph coloring
- backtracking search
- combinatorial problems
- sat solving
- polynomial size
- davis putnam
- maximum satisfiability
- approximation algorithms
- propositional logic
- constraint programming
- temporal logic
- propositional formulas
- computational properties
- orders of magnitude
- lower bound
- np hard
- heuristic search
- boolean variables
- quantified boolean formulas
- computational complexity
- acyclic conjunctive queries
- search algorithm