Editing Boolean satisfiability problem (section)

===Schaefer's dichotomy theorem===
{{Main|Schaefer's dichotomy theorem}}
The restrictions above (CNF, 2CNF, 3CNF, Horn, XOR-SAT) bound the considered formulae to be conjunctions of subformulas; each restriction states a specific form for all subformulas: for example, only binary clauses can be subformulas in 2CNF.

Schaefer's dichotomy theorem states that, for any restriction to Boolean functions that can be used to form these subformulas, the corresponding satisfiability problem is in P or NP-complete.  The membership in P of the satisfiability of 2CNF, Horn, and XOR-SAT formulae are special cases of this theorem.<ref name="schaefer"/>

The following table summarizes some common variants of SAT.
{| class="wikitable sortable"
|+
!Code
!Name
!Restrictions
!Requirements
!Class
|-
|3SAT
|3-satisfiability
|Each clause contains 3 literals.
|At least one literal must be true.
|NP-c
|-
|2SAT
|2-satisfiability
|Each clause contains 2 literals.
|At least one literal must be true.
|NL-c
|-
|1-in-3-SAT
|Exactly-1 3-SAT
|Each clause contains 3 literals.
|Exactly one literal must be true.
|NP-c
|-
|1-in-3-SAT+
|Exactly-1 Positive 3-SAT
|Each clause contains 3 positive literals.
|Exactly one literal must be true.
|NP-c
|-
|NAE3SAT
|Not-all-equal 3-satisfiability
|Each clause contains 3 literals.
|Either one or two literals must be true.
|NP-c
|-
|NAE3SAT+
|Not-all-equal positive 3-SAT
|Each clause contains 3 positive literals.
|Either one or two literals must be true.
|NP-c
|-
|PL-SAT
|[[Planar SAT]]
|The incidence graph (clause-variable graph) is [[Planar graph|planar]].
|At least one literal must be true.
|NP-c
|-
|LSAT
|Linear SAT
|Each clause contains 3 literals, intersects at most one other clause, and the intersection is exactly one literal.
|At least one literal must be true.
|NP-c
|-
|HORN-SAT
|Horn satisfiability
|Horn clauses (at most one positive literal).
|At least one literal must be true.
|P-c
|-
|XOR-SAT
|Xor satisfiability
|Each clause contains XOR operations rather than OR.
|The XOR of all literals must be true.
|P
|}