Determining satisfiability of 3-SAT in polynomial time.
Ortho FlintAsanka WickramasingheJason BrasseChristopher FowlerPublished in: CoRR (2019)
Keyphrases
- satisfiability problem
- sat problem
- boolean formula
- sat solving
- phase transition
- satisfiability testing
- stochastic local search
- sat instances
- computational complexity
- sat solvers
- sat encodings
- np complete
- temporal logic
- davis putnam
- special case
- propositional logic
- search algorithm
- davis putnam logemann loveland
- boolean satisfiability
- propositional satisfiability
- stochastic local search algorithms
- cnf formula
- max sat
- randomly generated
- conjunctive normal form
- constraint satisfaction problems
- backtracking search
- random sat
- clause learning
- belief revision