3-SAT

(x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₄ ∨ x₅) 처럼, 변수나 그 부정 세 개를 OR 로 묶은 절(clause)들을 AND 로 이은 식의 충족 가능성을 묻는다. 꼴을 이렇게 제한해도 여전히 NP-완전이다. 구조가 단순해서 다른 문제가 NP-완전임을 보일 때 환산의 출발점으로 가장 자주 쓰인다. 무작위로 만든 3-SAT 식은 절 수와 변수 수의 비가 약 4.27 근처일 때 가장 풀기 어렵다는 것이 실험으로 관찰되어 있다.