충족 가능성 문제(SAT)

참·거짓 값을 갖는 변수들을 AND(∧), OR(∨), NOT(¬)으로 엮은 논리식이 주어질 때, 식 전체를 참으로 만드는 변수 값이 있는지 묻는다(만족 가능성 문제라고도 한다). 처음으로 NP-완전임이 증명된 문제다. 변수가 n 개면 값을 넣는 방법이 2ⁿ 가지인데, 이를 근본적으로 줄이는 다항 시간 방법은 알려져 있지 않다. 그런데도 현대의 SAT 풀이 프로그램은 변수가 수백만 개인 산업 현장의 사례를 자주 풀어낸다. 최악의 경우와 실제 사이의 이 간극도 연구 주제다.