A Linear Complementarity Theorem to solve any Satisfiability Problem in conjunctive normal form in polynomial time.
Giacomo PatriziPublished in: CoRR (2018)
Keyphrases
- satisfiability problem
- conjunctive normal form
- polynomial size
- np complete
- temporal logic
- search algorithm
- phase transition
- sat instances
- sat problem
- boolean formula
- computational complexity
- stochastic local search
- dnf formulas
- bounded treewidth
- constraint satisfaction
- special case
- linear constraints
- randomly generated