쿡-레빈 정리

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

 증명 

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

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

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

변수의미변수 전체 개수테이프 셀 가 번째 계산에서 기호 를 가지는 경우 참의 테이프 헤드가 번째 계산에서 테이프 셀 에 있으면 참이 번째 계산에서 상태 에 있으면 참

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

논리식논리식 조건논리식의 의미논리식 전체 개수테이프 셀 가 기호 를 값으로 갖는 경우테이프의 초기 값을 표현한다. 과 의 경우 셀의 값은 이다.의 초기 상태를 표현한다.1테이프 헤드의 초기 위치를 표현한다.1테이프 셀이 여러 개의 심볼 값을 동시에 가지지 않는다는 것을 표현한다.쓰기 명령이 아닌 경우 테이프의 헤드 위치가 바뀌지 않는다는 것을 표현한다.기계가 여러 개의 상태를 동시에 가지지 않는다.테이프 헤드가 동시에 여러 위치에 있지 않는다.번째 계산에서 테이프 헤드가 에 있을 모든 가능성을 표현한다.계산이 끝난 후의 테이프 값을 표현한다.1

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

 출처 

분류:계산 복잡도 이론