====== 쿡-레빈 정리 ======

[[en>Cook-Levin theorem]]. [[SAT]]가 [[NP-완전]]함을 증명한다.

기본적인 아이디어는 비결정적 [[튜링기계]](NTM)를 [[다항시간]] 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) [[NP복잡도|NP]]의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다.

{{tag>전산학}}