쿡-레빈 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

쿡-레빈 정리는 모든 NP 문제가 부울 만족 문제(SAT)로 다항 시간 안에 환원될 수 있음을 증명한다. 이 정리는 SAT가 NP-완전 문제임을 보이며, P 대 NP 문제 해결에 중요한 단서를 제공한다. 쿡-레빈 정리는 스티븐 쿡과 레오니드 레빈에 의해 독립적으로 발표되었으며, 튜링상 수상의 기반이 되었다. 쿡-레빈 정리는 카프의 21개 NP-완전 문제 목록 제시의 기반이 되었으며, 복잡도 이론과 관련된 다양한 문제의 연구에 영향을 미쳤다.

쿡-레빈 정리

📚 더 읽어볼만한 페이지

계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간

1. 개요
2. 역사적 배경
3. 정의
4. 쿡-레빈 정리 증명
- 4.1. SAT ∈ NP
- 4.2. 모든 NP 문제의 SAT 환원
5. 복잡도
6. 의의 및 영향
7. P-NP 문제와 연관성

2. 역사적 배경

스티븐 쿡은 1971년 전산 이론 심포지엄에서 "정리 증명 절차의 복잡성"이라는 논문을 발표하여 NP-완전 개념의 기초를 마련했다. 리처드 카프는 "조합 문제 간의 환원 가능성"이라는 논문에서 21개의 NP-완전 문제 목록을 제시하며 쿡의 연구를 발전시켰다. 쿡과 카프는 이 연구로 튜링상을 수상했다.

소련의 레오니드 레빈도 "보편적 탐색 문제"라는 논문을 발표하여 NP-완전 문제 연구에 기여했다. 레빈은 해결책을 찾는 탐색 문제를 다루었다는 점에서 쿡, 카프와 차이가 있었다.

1975년, 테오도어 P. 베이커, 존 길, 로버트 솔로베이는 특정 오라클 기계 모델에서 NP 문제를 해결하려면 지수 시간이 필요함을 보였다. 이는 P^A ≠ NP^A임을 보여 P ≠ NP 추측을 뒷받침하는 중요한 결과이다.

3. 정의

NP에 속하는 결정 문제는 비결정적 튜링 기계가 다항 시간 내에 이 문제를 결정할 수 있다는 의미이다.

불 만족 문제의 사례는 불 변수들을 논리 연산자를 사용하여 결합한 불 대수식이다. 이러한 식은 전체 식을 참으로 만드는 변수에 대한 진리값 할당이 존재할 경우 만족가능하다고 한다.

4. 쿡-레빈 정리 증명

쿡-레빈 정리는 SAT 문제가 NP에 속하며, 모든 NP 문제를 SAT 문제로 다항 시간 안에 환원할 수 있음을 보인다. 이 증명은 NP 문제의 검증 과정을 논리식으로 표현하고, 이 논리식이 만족 가능한지 판별하는 SAT 문제로 변환하는 방식으로 이루어진다.

쿡의 M을 SAT로 줄이는 것을 보여주는 교환도. 데이터 크기와 프로그램 실행 시간은 각각 주황색과 녹색으로 표시되어 있다. — 쿡의 $M$ 을 SAT로 줄이는 것을 보여주는 교환도. 데이터 크기와 프로그램 실행 시간은 각각 주황색과 녹색으로 표시되어 있다.

머신 M에 의한 허용된 계산의 개략도. — 머신 $M$ 에 의한 허용된 계산의 개략도.

NP에 속하는 임의의 결정 문제에 대해, 다항 시간 내에 문제를 해결하는 비결정적 튜링 기계가 존재한다. 이 기계에 특정 입력을 주었을 때, 기계가 올바르게 실행되어 "예"라고 답하는지 여부를 계산하는 부울 식을 만들 수 있다. 이 부울 식은 기계가 올바르게 실행되어 "예"라고 답하는 경우에만 만족 가능하므로, 부울 식의 만족 가능성 여부는 기계가 "예"라고 답할지 여부와 동일하다.

4.1. SAT ∈ NP

주어진 논리식과 각 변수의 값 할당이 주어졌을 때, 그 논리식이 참인지 거짓인지는 결정적 튜링 머신에 의해 다항 시간 안에 검증될 수 있다. 따라서 SAT는 NP에 속한다.

4.2. 모든 NP 문제의 SAT 환원

임의의 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}$	테이프 셀 $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$	$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_{qk}

를

B

에 대입했을 때

B

는 참값을 갖는다. 반대로

B

가 참인 경우

M

이 입력을 받아들이는 계산이 존재한다.

B

를 생성하는데 다항 시간이 소요되므로, NP 문제를 SAT로 다항 시간 안에 환원하는 것이 가능하다.

5. 복잡도

쿡-레빈 정리의 원래 증명은 비결정적 튜링 기계를 `O(log(p(n))p(n)^3)`의 복잡도로 인코딩한다. 그러나 문헌에서는 더 정교한 접근 방식을 통해 `O(p(n)log(p(n)))`의 복잡도를 갖는 인코딩 방법을 설명한다. 이러한 준선형 결과는 쿡의 원래 논문 발표 후 7년 뒤에 처음 등장했다.

6. 의의 및 영향

쿡-레빈 정리는 모든 NP 문제가 SAT 문제로 환원될 수 있음을 보여주어, SAT가 NP-완전 문제임을 증명했다. 이는 P-NP 문제 해결에 중요한 단서를 제공한다. 만약 SAT를 다항 시간 안에 풀 수 있다면, 모든 NP 문제를 다항 시간 안에 풀 수 있으므로 P=NP가 된다.

리처드 카프는 쿡-레빈 정리를 바탕으로 21개의 다양한 NP-완전 문제를 제시하여 NP-완전성 개념을 널리 알렸다. 그는 다른 문제(이미 NP-완전으로 증명된)를 해당 문제로 축소함으로써 각 문제가 NP-완전임을 보였다. 예를 들어, 3SAT(절당 정확히 세 개의 변수 또는 변수의 부정으로 이루어진 결합 정규 형식 (CNF)의 표현에 대한 부울 만족 문제) 문제가 NP-완전임을 보였다.

개리와 존슨은 저서 컴퓨터와 난해성: NP-완전성 이론 안내서(Computers and Intractability: A Guide to the Theory of NP-Completeness)에서 300개 이상의 NP-완전 문제를 제시했으며, 새로운 문제들이 여전히 해당 복잡도 종류 내에 있는 것으로 발견되고 있다.

7. P-NP 문제와 연관성

SAT 문제, 더 나아가 NP-완전 문제에 대한 다항 시간 알고리즘이 존재하는지 여부는 여전히 미해결 난제이다. (P 대 NP 문제) 많은 학자들이 이 문제에 도전하고 있지만, 아직까지 해결되지 않고 있다. SAT의 많은 실제 인스턴스가 휴리스틱 방법으로 해결될 수 있지만, SAT(및 결과적으로 모든 다른 NP-완전 문제)에 대한 결정적 다항 시간 알고리즘이 있는지 여부는 복잡도 이론가, 수리 논리학자 및 기타 전문가들의 수십 년간의 치열한 노력에도 불구하고 여전히 해결되지 않은 유명한 문제이다.