SAT

可满足性问题 $SAT=\{<\varphi >|\varphi \text{是可满足的布尔公式}\}$

二元可满足性问题 $2SAT=\{<\varphi >|\varphi \text{是可满足的}2cnf\}$, $2SAT\in P$.

三元可满足性问题 $3SAT=\{<\varphi >|\varphi \text{是可满足的}3cnf\}$, $3SAT\in NP$.