# Dichotomy Theorems
Every Boolean constraint satisfiable problem is either in or -complete.
2SAT
、 Horn-SAT
、 XOR-SAT
,else in -complete.
Bulatov['02] extends the theorem to the ternary constraint satisfiable problem (the size of alphabet is 3), such as 3-Coloring.
ternary constraint satisfiable problems are either in or -complete.
# Ladner’s Theorem
If , then such that and -complete.