====== 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((원래 버전인 MONOTONE-3-SAT는 물론 졸라 쉽다.)) 모두 NP-완전이다!

{{tag>전산학}}