k-CNF SAT(k-SAT)는 각 절(clause)에 리터럴이 최대 k개씩 들어 있는 논리곱 표준형(CNF) Boolean 논리식에 대해, 모든 절을 동시에 참으로 만드는 변수 값 배정이 있는지 묻는 결정 문제다. 충족 가능성 문제(SAT)의 특수한 경우로, 2-SAT는 다항 시간에 풀리지만 3-SAT를 비롯해 k가 3 이상이면 NP-완전이다.
SAT는 1971년 Stephen Cook이 NP-완전임을 증명한 최초의 문제이며, 3-SAT는 다른 문제의 NP-난해성을 보이는 환원의 출발점으로 널리 쓰인다. 변수가 n개일 때 모든 배정을 시험하면 2^n 시간이 들고, 2^{cn}(c<1) 시간에 동작하는 알고리즘들이 알려져 있다. 지수 시간 가설(ETH)은 이 문제를 준지수 시간에 풀 수 없다는 추측이다. 실무에서는 SAT 솔버가 하드웨어·소프트웨어 검증과 계획 문제 등에 쓰인다.