쿡–레빈 정리

NP 의 모든 문제가 다항 시간에 SAT 로 환산된다는 정리다. 증명의 뼈대는, 다항 시간 검증자의 계산 과정 전체를 「이 식이 충족 가능하다 ⇔ 검증자가 받아들이는 증거가 있다」가 되도록 하나의 논리식으로 옮겨 적는 것이다. 스티븐 쿡이 1971년에, 레오니트 레빈이 소련에서 독립적으로(1973년 출판) 증명했다. 이 정리 덕분에 다른 문제의 NP-완전성은 SAT 에서 그 문제로 가는 환산 하나만 보이면 된다.