# Dichotomy Theorems

Every Boolean constraint satisfiable problem is either in PP or NPNP-complete.

2SATHorn-SATXOR-SAT P\in P,else in NPNP-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 PP or NPNP-complete.

# Ladner’s Theorem

If PNPP\neq NP, then LNP\exists L\in NP such that LPL\notin P and LNPL\notin NP-complete.