SAT

충족 가능성(satisfiability) 문제. 요컨대 \wedge(AND)랑 \vee(OR)이랑 \neg(NOT)이랑 변수들로 이루어진 수식이 있을 때, 이 수식의 변수들에 적절히 참이나 거짓을 끼워 넣어서 전체 수식을 참으로 만들 수 있는지 묻는다.

쿡-레빈 정리에 따라서 SAT는 NP-완전하며, 사실 처음으로 NP-완전임이 증명되었다. 게다가 워낙 일반적인 문제기도 해서 다양한 변종이 알려져 있다.

• 2-SAT는 입력 수식을 2-CNF로 제한한 것으로, \mathrm{O}(n) 시간에 풀 수 있다.
• 3-SAT는 입력 수식을 3-CNF로 제한한 것으로, 원래 SAT 인스턴스를 3-CNF로 다항시간 안에 바꿀 수 있는 관계로 마찬가지로 NP-완전이다.
• NAE-3-SAT("Not all equal")는 3-SAT와 유사하지만 각 항의 변수 중 하나 이상이 참이고 다른 하나 이상이 거짓이어야 한다. 이 문제와, 일반화된 NAE-SAT, 그리고 변수들에 \neg이 안 붙은 MONOTONE-NAE-3-SAT¹⁾ 모두 NP-완전이다!