复杂性中的一些结论 (无证明)

Every Boolean constraint satisfiable problem is either in $P$ or $NP$-complete.

2SAT 、 Horn-SAT 、 XOR-SAT $\in P$，else in $NP$-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 $P$ or $NP$-complete.

If $P\neq NP$, then $\exists L\in NP$ such that $L\notin P$ and $L\notin NP$-complete.