쿡-레빈 정리

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

증명

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

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

크기 $n$인 입력에 대해 $M$이 최대 $p(n)$번의 계산 후 멈춘다고 가정하자. 다음과 같은 변수들을 정의한다. 여기에서 $-p(n)\leq i\leq p(n)$, $j\in \Sigma$, $0\leq k\leq p(n)$, $q\in Q$이다.

변수	의미	변수 전체 개수
$T_{ijk}$	테이프 셀 $i$가 $k$번째 계산에서 기호 $j$를 가지는 경우 참	$O(p(n)^{2})$
$H_{ik}$	$M$의 테이프 헤드가 $k$번째 계산에서 테이프 셀 $i$에 있으면 참	$O(p(n)^{2})$
$Q_{qk}$	$M$이 $k$번째 계산에서 상태 $q$에 있으면 참	$o(p(n))$

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

논리식	논리식 조건	논리식의 의미	논리식 전체 개수
$T_{ij0}$	테이프 셀 $i$가 기호 $j$를 값으로 갖는 경우	테이프의 초기 값을 표현한다. $i>n-1$과 $i<0$의 경우 셀의 값은 $\sqcup$이다.	$O(p(n))$
$Q_{s0}$		$M$의 초기 상태를 표현한다.	1
$H_{00}$		테이프 헤드의 초기 위치를 표현한다.	1
$T_{ijk}\to \lnot T_{ij'k}$	$j\not =j'$	테이프 셀이 여러 개의 심볼 값을 동시에 가지지 않는다는 것을 표현한다.	$O(p(n)^{2})$
$T_{ijk}\land T_{ij'(k+1)}\to H_{ik}$	$j\not =j'$	쓰기 명령이 아닌 경우 테이프의 헤드 위치가 바뀌지 않는다는 것을 표현한다.	$O(p(n)^{2})$
$Q_{qk}\to \lnot Q_{q'k}$	$q\not =q'$	기계가 여러 개의 상태를 동시에 가지지 않는다.	$O(p(n))$
$H_{ik}\to \lnot H_{i'k}$	$i\not =i'$	테이프 헤드가 동시에 여러 위치에 있지 않는다.	$O(p(n)^{3})$
$(H_{ik}\land Q_{qk}\land T_{i\sigma k})\to$ $\bigvee _{(q,\sigma ,q',\sigma ',d)\in \delta }(H_{(i+d)(k+1)}\land Q_{q'(k+1)}\land T_{i\sigma '(k+1)})$	$k<p(n)$	$k$번째 계산에서 테이프 헤드가 $i$에 있을 모든 가능성을 표현한다.	$O(p(n)^{2})$
$\bigvee _{f\in F}Q_{fp(n)}$		계산이 끝난 후의 테이프 값을 표현한다.	1

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