2-SAT

절마다 변수나 그 부정이 두 개씩인 식의 충족 가능성 문제다. 절 (a ∨ b) 를 「a 가 거짓이면 b 는 참」이라는 함의로 바꿔 그래프를 만들면 입력 크기에 비례하는 시간에 풀 수 있으므로 P 에 속한다. 항의 수가 2 에서 3 으로 바뀌는 순간 쉬운 문제가 NP-완전 문제가 된다는 점에서, 쉬움과 어려움의 경계를 보여 주는 예다. P ≠ NP 증명이라고 주장하는 논증은 「왜 같은 논증이 2-SAT 에는 통하지 않는가」를 설명할 수 있어야 한다.