Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems.
Stefan PorschenEwald SpeckenmeyerPublished in: SAT (Selected Papers (2004)
Keyphrases
- np complete
- sat problem
- np hard
- worst case bounds
- satisfiability problem
- random sat instances
- worst case
- randomly generated
- constraint satisfaction problems
- max sat
- boolean satisfiability
- phase transition
- propositional satisfiability
- sat instances
- computational complexity
- stochastic local search
- np complete problems
- davis putnam
- special case
- sat solving
- optimal solution
- lower bound
- conjunctive queries
- cnf formula
- sat solvers
- horn clauses
- genetic algorithm
- clause learning
- propositional logic
- branch and bound algorithm
- polynomial time complexity
- backtracking search
- decision problems
- constraint satisfaction