쿡-레빈 정리

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

증명

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

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

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

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

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

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

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

출처

1. Michael R. Garey, David S. Johnson (1979). 《Computers and Intractability: A Guide to the Theory of NP-Completeness》. W. H. Freeman. ISBN 0-7167-1045-5.