SATISFIABILITY PROBLEM

Satisfiability problem (SAT). Find a truth assignment to logical propositions such that a (given) collection of clauses is true (or ascertain that at least one clause must be false in every truth assignment). This fundamental problem in computational logic forms the foundation for NP-completeness . When SAT is in CNF and may not be satisfiable, we define the problem of maximizing the number of true clauses as MAXSAT.