쿡-레빈 정리

3. 정의

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

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

4. 쿡-레빈 정리 증명

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

4. 1. SAT ∈ NP

4. 2. 모든 NP 문제의 SAT 환원

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

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

5. 복잡도

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

6. 의의 및 영향

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

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

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

7. P-NP 문제와 연관성

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

참조

_[1] 서적 The complexity of theorem proving procedures
_[2] 간행물 Relativizations of the P = NP question
_[3] 간행물 On the impossibility of eliminating exhaustive search in computing a function relative to its graph
_[4] 간행물 Универсальные задачи перебора http://www.mathnet.r[...]
_[5] 문서 This column uses the big O notation.
_[6] 문서 The number of literals in each clause does not depend on $n$, except for the last table row, which leads to a clause with $O(p(n))$ literals.
_[7] 간행물 Satisfiability is quasilinear complete in NQL https://www.ccs.neu.[...] 1978-01
_[8] 간행물 Relations among complexity measures https://www.ccs.neu.[...] 1979-04
_[9] conference A new proof of the NP completeness of satisfiability null null 1979-02
_[10] 간행물 An $O(T\; \backslash log\; T)$ reduction from RAM computations to satisfiability 1991-05
_[11] 간행물 Short propositional formulas represent nondeterministic computations https://www.ccs.neu.[...] 1988-01
_[12] conference Multiple-person alternation https://ieeexplore.i[...] IEEE
_[13] 간행물 Lower bounds for multiplayer noncooperative games of incomplete information 2001-04
_[14] 서적 Reducibility Among Combinatorial Problems Plenum
_[15] 문서 First modify the proof of the Cook–Levin theorem, so that the resulting formula is in conjunctive normal form, then introduce new variables to split clauses with more than 3 atoms. For example, the clause $(A\; \backslash lor\; B\; \backslash lor\; C\; \backslash lor\; D)$ can be replaced by the conjunction of clauses $(A\; \backslash lor\; B\; \backslash lor\; Z)\; \backslash land\; (\backslash lnot\; Z\; \backslash lor\; C\; \backslash lor\; D)$, where $Z$ is a new variable that will not be used anywhere else in the expression. Clauses with fewer than three atoms can be padded; for example, $(A\; \backslash lor\; B)$ can be replaced by $(A\; \backslash lor\; B\; \backslash lor\; B)$.
_[16] 서적 Computers and Intractability: A Guide to the Theory of NP-Completeness W. H. Freeman and Company
_[17] 서적 https://archive.org/[...]