쿡-레빈 정리

쿡-레빈 정리(Cook-Levin theorem)는 충족 가능성 문제(SAT)가 NP-완전이라는 것을 증명하는 정리로, 모든 NP 복잡도에 속하는 결정 문제는 다항 시간 내에 충족 가능성 문제로 환산할 수 있다는 것을 의미한다.
스티븐 쿡과 레오니드 레빈의 이름을 따서 지어졌다.

증명 

쿡-레빈 정리는 다음과 같이 증명할 수 있다.
먼저 SAT가 NP에 속한다는 것은 논리식과 각 변수의 값이 주어졌을 때 그 논리식이 참인지 거짓인지를 다항 시간 내에 검증할 수 있다는 것으로 증명된다.

임의의 NP 문제를 다항 시간 내에 SAT로 변환하기 위해, NP 문제에 대응하는 논리식을 다음과 같이 구성한다.
우선 주어진 NP 문제에 대해, 그 문제를 검증할 수 있는 비결정론적 튜링 기계 이 존재한다. 이때 는 상태의 집합, 는 테이프 기호의 집합, 는 초기 상태, 는 빈 심볼, 는 최종 상태의 집합, 는 전이함수이다.

크기 인 입력에 대해 이 최대 번의 계산 후 멈춘다고 가정하자. 다음과 같은 변수들을 정의한다. 여기에서 , , , 이다.

이제 이 변수들을 이용하여 다음의 논리식들을 정의한다.

마지막으로, 논리식 을 위에서 정의한 모든 논리식의 논리곱으로 정의한다.
만약 이 어떤 입력을 받아들일 경우, 그 계산에 대응하는 를 에 대입했을 때 는 참의 값을 갖는다. 반대로 가 참인 경우 이 입력을 받아들이는 계산이 존재한다.
를 생성하는 데에 다항 시간이 소요되므로, NP 문제를 SAT로 다항 시간 내에 환원하는 것이 가능하다.

출처 

계산 복잡도 이론