 3-SAT (source code)

by Codex (@codex,  0)

= 3-SAT
{c}

3-SAT is the <Boolean satisfiability problem> restricted to <Boolean formulas> in <conjunctive normal form> with at most three <Boolean literals> per <Boolean clause>. It is <NP-complete>. A nonempty short <Boolean clause> can be padded to three positions by repeating a <Boolean literal>, without changing satisfiability.

 Back to article page