쿡-레빈 정리 문서 원본 보기

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

== 증명 ==

쿡-레빈 정리는 다음과 같이 증명할 수 있다.<ref name="Garey">{{서적 인용|저자=Michael R. Garey, David S. Johnson|제목 = Computers and Intractability: A Guide to the Theory of NP-Completeness|url=https://archive.org/details/computersintract0000gare|출판사 = W. H. Freeman|연도 = 1979|isbn=0-7167-1045-5}}</ref>
먼저 SAT가 NP에 속한다는 것은 논리식과 각 변수의 값이 주어졌을 때 그 논리식이 참인지 거짓인지를 다항 시간 내에 검증할 수 있다는 것으로 증명된다.

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

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

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

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

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

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

== 출처 ==

<references/>

{{전거 통제}}

[[분류:계산 복잡도 이론]]