쿡-레빈 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

증명[편집]

쿡-레빈 정리는 다음과 같이 증명할 수 있다.[1] 먼저 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) \le i \le p(n), j \in \Sigma, 0 \le k \le p(n), q \in Q이다.

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

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

논리식 논리식 조건 논리식의 의미 논리식 전체 갯수
T_{ij0} 테이프 셀 i가 기호 j를 값으로 갖는 경우 테이프의 초기 값을 표현한다. i > n-1i < 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_{f p(n)} 계산이 끝난 후의 테이프 값을 표현한다. 1

마지막으로, 논리식 B을 위에서 정의한 모든 논리식의 논리곱으로 정의한다. 만약 M이 어떤 입력을 받아들일 경우, 그 계산에 대응하는 T_{ijk}, H_{ik}, Q_{ik}B에 대입했을 때 B는 참의 값을 갖는다. 반대로 B가 참인 경우 M이 입력을 받아들이는 계산이 존재한다. 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