Conjunctive Normal Form SAT
CNF-SAT restricts the boolean formula to conjunctive normal form (CNF), meaning it is the AND of ORs.
Parameters
- : number of variables
Related Problems
- SAT2
Filters
Computational Model
Randomization
Approximation
Algorithms Table
Displaying 5 of 5 algorithms
| See more | ||||
|---|---|---|---|---|
| Quantum Adiabatic Algorithm (QAA) | 2001 | O(2^n) | O(poly(n)) | |
| Conflict-Driven Clause Learning (CDCL) | 1999 | O(2^n) | ||
| WalkSAT | 1994 | O(n*mt*mf) | O(n) | |
| GSAT | 1992 | O(n*mt*mf) | O(n) | |
| Davis-Putnam-Logemann-Loveland Algorithm (DPLL) | 1961 | O(2^n) | O(n) |
Reductions Table
Displaying 24 of 24 reductions
Other relevant algorithms
Insuffient Data to display table