쿡-레빈 정리

계산 복잡도 이론에서, 쿡-레빈 정리(Cook-Levin theorem)는 부울 만족도 문제가 NP-완전이라는 것을 말합니다. 즉, NP에 있으며, NP의 모든 문제는 결정론적 튜링 기계에 의해 부울 만족도 문제로 다항 시간 내에 감소될 수 있습니다.

이 정리는 스티븐 쿡과 레오니드 레빈의 이름을 따서 지어졌습니다.

이 정리의 중요한 결과는 부울 만족도를 해결하기 위한 결정론적 다항 시간 알고리즘이 존재하면 모든 NP 문제를 결정론적 다항 시간 알고리즘으로 해결할 수 있다는 것입니다. 따라서 이러한 부울 만족도에 대한 알고리즘이 존재하는지에 대한 질문은 2023년^[update] 현재 이론 컴퓨터 과학에서 여전히 가장 중요한 해결되지 않은 문제로 널리 간주되는 P 대 NP 문제와 동등합니다.

분담금

NP-완전성의 개념은 북미와 소련의 연구자들에 의해 1960년대 후반과 1970년대 초반에 동시에 개발되었습니다. 1971년 스티븐 쿡은 새로 설립된 ACM 컴퓨팅 이론 심포지엄의 회의 절차에서 논문 "정리 증명 절차의 복잡성"^[1]을 발표했습니다. Richard Karp의 후속 논문인 "조합 문제들 사이의 환원성"^[2]은 21개의 NP-완전 문제 목록을 제공함으로써 쿡의 논문에 대한 새로운 관심을 불러일으켰습니다. Karp는 또한 NP-완전성의 현재 정의에 사용되는 완전성의 개념(즉, 다항식-시간 다중-원 감소에 의한)을 소개했습니다. 쿡과 카프는 각각 이 작품으로 튜링상을 받았습니다.

NP-완전성에 대한 이론적 관심은 1975년 특정 오라클 머신 모델에서 NP-문제를 해결하는 데 지수 시간이 필요하다는 것을 보여준 Theodore P. Baker, John Gill, Robert Solovay의 연구에 의해서도 향상되었습니다. 즉, 모든 하위 지수 결정론적-시간 복잡도 클래스 T에 대하여 상대화 복잡도 클래스 NP가^A T의^A 부분 집합이 아닌 오라클 A가 존재합니다. 특히 이 오라클의 경우 P ≠ NP.

소련에서는 1969년에 M이 Baker, Gill, Solovay와 동등한 결과를 발표했습니다. 데크티아르.^[4] 이후 레오니드 레빈의 논문인 "Universal search problems"^[5]가 1973년에 발표되었지만, 이는 회담에서 언급되었고 몇 년 전에 출판을 위해 제출되었습니다.

레빈의 접근 방식은 단순히 존재를 판단하는 것이 아니라 해결책을 찾아야 하는 탐색 문제를 고려했다는 점에서 쿡과 카프의 접근 방식과 약간 달랐습니다. 그는 6개의 그러한 NP-완전 검색 문제, 즉 보편적인 문제를 제공했습니다. 또한 그는 이러한 문제 각각에 대해 최적의 시간에 이를 해결하는 알고리즘을 발견했습니다(특히 이러한 알고리즘은 P = NP인 경우에만 다항식 시간에 실행됩니다).

정의들

결정 문제는 다항 시간에 비결정론적 튜링 기계에 의해 결정될 수 있다면 NP에 있습니다.

부울 만족도 문제의 예로는 부울 연산자를 사용하여 부울 변수를 결합하는 부울 식을 들 수 있습니다. 이러한 표현식은 전체 표현식을 참으로 만드는 변수에 진리값이 어느 정도 할당되어 있으면 만족됩니다.

아이디어

NP에서 어떤 결정 문제가 주어졌을 때, 다항 시간 내에 그것을 해결하는 비결정론적 기계를 구성합니다. 그런 다음 해당 기계에 대한 각 입력에 대해 특정 입력이 기계에 전달되면 기계가 올바르게 실행되고 기계가 중단되어 "예"라고 대답하는지 계산하는 부울 식을 작성합니다. 그러면 기계가 올바르게 작동하여 "예"라고 대답할 수 있는 방법이 있어야만 표현식이 만족될 수 있으므로, 구성된 표현식의 만족도는 기계가 "예"라고 대답할지 여부를 묻는 것과 같습니다.

증명

이 증명은 Garey & Johnson 1979, 페이지 38-44, 섹션 2.6에 의해 제공된 것을 기반으로 합니다.

부울 만족도 문제(SAT)가 NP-complete임을 증명하는 데는 두 가지 부분이 있습니다. 하나는 SAT가 NP 문제라는 것을 보여주는 것입니다. 다른 하나는 모든 NP 문제가 다항식-시간 다원 감소에 의해 SAT 문제의 예로 감소될 수 있음을 보여주는 것입니다.

주어진 식을 만족한다고 주장되는 부울 변수에 대한 부울 값의 할당은 결정론적 튜링 기계에 의해 다항식 시간 내에 검증될 수 있기 때문에 SAT는 NP에 있습니다. (다항 시간에서 결정론적 튜링 기계에 의해 검증 가능하고 비결정론적 튜링 기계에 의해 다항 시간에서 해결 가능한 문장은 동등하며, 증명은 많은 교과서, 예를 들어 Sipser의 계산 이론 소개 섹션 7.3은 물론 NP에 대한 위키피디아 기사에서 찾을 수 있습니다.)

이제 NP의 주어진 문제가 비결정론적 튜링 기계 $M$ =${\displaystyle }$(${\displaystyle Q,}$σ$,$ s, F, δ) {\$displaystyle$ M = (Q,\Sigma,s,F,\delta )}에 의해 해결될 수 있다고 가정합니다. 여기서 Q {\displaystyle Q}는 상태 집합, σ {\displaystyle \Sigma}는 테이프 기호의 알파벳, s ∈ Q {\displaystyle s\in Q}는 초기 상태, $F ⊆$ Q ${\displaystyle$ F$\subseteq$ Q}는 수용 상태의 집합이고${\displaystyle ,}$ δ ${\displaystyle \subseteq }$(Q ∖ F ) × (${\displaystyle Q}$ ${\displaystyle \times }$ σ σ × { - 1, + 1}) {\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma)\times (Q\times \Sigma \times \{-1,+1\})}는 전이 관계입니다. $M{\displaystyle }$ ${\displaystyle$ M$}$이(가) $최대{\displaystyle }$ p${\displaystyle (n)}$ ${\displaystyle p(n)}$ 계산$$ 단계 후에 문제의 인스턴스를 받아들이거나$$ 거부한다고 가정합니다. 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 인스턴스의 크기이고 p ${\displaystyle$ p$}$은 다항 함수입니다.

$I{\displaystyle }$ ${\displaystyle$ I$}$은(는) 각 입력에 $M$ {\$displaystyle$ M$}$ $시스템$이 I {\$displaystyle$ I$$$}$을(를$)$ 받아들이는 경우에만$$ 만족되는 $부울{\displaystyle }$ 식$$B {\$displaystyle$ B$}$을(를$)$ 지정합니다$.$

부울 식은 다음 표에 제시된 변수를 사용합니다. 여기서 $q$∈ Q ${\$$displaystyle$$$q\in Q}는 기계 상태, - p ( n ) ≤ i ≤ p ( n ) {\displaystyle -p(n)\leq i\leq p(n)}는 테이프 위치, j ∈ σ {\displaystyle j\in \Sigma}는 테이프 심볼, 0 ≤ k ≤ p ( n) {\displaystyle 0\leq k\leq p(n)}는 계산 단계의 개수입니다.

변수	의도된 해석	몇 개?[6]
${\displaystyle T_{i,j,k}}$	테이프 셀 $i{\displaystyle }$ ${\displaystyle i}$에 계산의$$ $k{\displaystyle }$ ${\displaystyle$ k$}$ 단계에서$$ 기호 $j{\displaystyle }$ ${\displaystyle j}$가 포함되어 있으면 true입니다.	${\displaystyle O(p(n)^{2}}$
${\displaystyle H_{i,k}}$	$계산$의 $k{\displaystyle }$${\$$displaystyle k}$ 단계에서 M {\$displaystyle$ $M$$\}$의 읽기/쓰기 헤드가 테이프 셀 $i{\displaystyle }$ ${\displaystyle$ i$}$에 있으면 true입니다.	${\displaystyle O(p(n)^{2}}$
${\displaystyle Q_{q,k}}$	계산의$$ 단계 $k{\displaystyle }${\$displaystyle$ k$}$에서 $M{\displaystyle }$ ${\displaystyle M}$이(가) $q{\displaystyle }$ ${\displaystyle q}$ 상태인 경우 참입니다.	${\displaystyle O(p(n))}$

${\displaystyle \mathrm{모든}}$ - p (${\displaystyle }$n ) ≤ i ≤ p ($$n ) $displaystyle -p(n)\leq$ i$\leq p(n)}$ 및 $0$ ${\displaystyle \le }$ ${\displaystyle k}$ ${\displaystyle \le }$ p${\displaystyle (n)}$ ${\displaystyle 0\leq$ k$\leq$ p$(n)}$에 대해 부울 식 $B{\displaystyle }$ ${\displaystyle$B}을 다음 표의 하위 식의 연결로 정의합니다$.$

표현	조건들	해석	몇 개나?
${\displaystyle T_{i,j,0}}$	$테이프$ 셀 $i{\displaystyle }$ ${\displaystyle$ i$}$에 처음에 기호 $j{\displaystyle }$ ${\displaystyle$ j$}$이(가) 포함되어 있습니다.	테이프의 초기 내용입니다. > n 1 {\$displaystyle$ i>$n-1}$ 및 < ${\displaystyle i<0}$의 경우$,$ 실제 $입력{\displaystyle }$ I$${\$displaystyle$ I$}$ 이외의 초기 기호는 특별한 기본/공백 기호입니다.	${\displaystyle O(p(n))}$
${\displaystyle Q_{s,0}}$		$M {\displaystyle$ M$}$의 초기 상태입니다$.$	1
${\displaystyle H_{0,0}}$		읽기/쓰기 헤드의 초기 위치.	1
${\displaystyle \neg T_{i,j,k}\lor \negT_{i,j'k}}$	${\displaystyle j\neq j'}$	테이프 셀 당 최대 한 개의 기호.	${\displaystyle O(p(n)^{2}}$
${\displaystyle \bigvee _{j\in \Sigma }T_{i,j,k}}$		테이프 셀당 하나 이상의 기호입니다.	${\displaystyle O(p(n)^{2}}$
${\displaystyle T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}}$	${\displaystyle j\neq j'}$	테이프는 머리로 쓰지 않으면 변하지 않습니다.	${\displaystyle O(p(n)^{2}}$
${\displaystyle \lnot Q_{q,k}\lor \lnot Q_{q,k}}$	${\displaystyle q\neq q'}$	한 번에 최대 한 가지 상태입니다.	${\displaystyle O(p(n))}$
${\displaystyle \bigve _{q\in Q}Q_{q,k}}$		한 번에 하나 이상의 상태.	${\displaystyle O(p(n))}$
${\displaystyle \lnot H_{i,k}\lor \lnot H_{i,k}}$	${\displaystyle i\neq'}$	한 번에 최대 한 개의 머리 위치.	${\displaystyle O(p(n)^{3})}$
${\displaystyle \bigvee _{-p(n)\leq i\leq p(n)}H_{i,k}}$		한 번에 하나 이상의 헤드 포지션.	${\displaystyle O(p(n)^{2}}$
${\displaystyle {\begin{array}{l}(H_{i,k}\land Q_{q,k}\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})\end{array}}}$	${\displaystyle k<p(n)}$	헤드가 $i{\displaystyle }$ ${\displaystyle i}$ 위치에 있을$$ 때 계산 단계 $k{\displaystyle }$ ${\displaystyle k}$에서 가능한 전환입니다$.$	${\displaystyle O(p(n)^{2}}$
${\displaystyle \bigvee _{0\leq k\leq p(n)}\bigvee _{f\in F}Q_{f,k}}$		$p{\displaystyle (n)}$ ${\displaystyle p(n)}$ 단계 이전에는 수락 상태에서 완료해야 합니다$.$	1

If there is an accepting computation for ${\displaystyle M}$ on input ${\displaystyle I}$, then ${\displaystyle B}$ is satisfiable by assigning ${\displaystyle T_{i,j,k}}$, ${\displaystyle H_{i,k}}$ and ${\displaystyle Q_{i,k}}$ their intended interpretations. 반면, $B{\displaystyle }$ ${\displaystyle B}$가 만족되면 $입력{\displaystyle }$ I$${\$displaystyle$ I$}$에 $M{\displaystyle }$ ${\displaystyle M}$에 대한 수락 계산이 있으며, 이는$$ 변수에 대한 할당에 의해 표시된 단계를 따릅니다.

$O{\displaystyle (p(n^{}}$ 2${\displaystyle {}^{}}$ ${\displaystyle$ O$(p(n)^{2)}$ 부울 변수가 있으며, 각각 공간 $O{\displaystyle (\log }$ ⁡${\displaystyle }$p($n))$ ${\displaystyle O(\$log$$p(n))}에서 인코딩할 수 있습니다. 절의 개수는 $O{\displaystyle (}$${\displaystyle p}$${\displaystyle (n^{}}$ 3${\displaystyle {}^{}}$ ${\displaystyle O(p(n)^{3}}$이므로 B ${\displaystyle$ B$}$의 크기는 O${\displaystyle (\log }$⁡(p${\displaystyle (n))p^{}}$(n${\displaystyle )}$ 3) {\$display O(\log(n)) p($n$)^\{$3}}입니다. 따라서 변환은 필요에 따라 다항식으로 여러 번 축소됩니다.

첫 번째 테이블 행(${\displaystyle {Ti,}_{}}$ ${\displaystyle {j,}_{}}$ ${\displaystyle 0_{}}$ ${\$만 실제로 입력 $문자열{\displaystyle }$ I ${\displaystyle I}$에 따라 달라집니다$.$ 나머지 라인은 입력 $길이{\displaystyle }$ n ${\displaystyle$ $n$$}$ 및$$ 시스템 $M{\displaystyle }$ ${\displaystyle$ $M$$}$에만 의존하며$,$ 최대 $p{\displaystyle (n)}$ ${\displaystyle p(n)}$ 단계에$$ 대한$$ $M{\displaystyle }$ ${\displaystyle M}$의 일반적인 계산을 공식화합니다.

변환은 다항식 $p{\displaystyle (n)}$ ${\displaystyle p(n)}$를 광범위하게 사용합니다$.$ 따라서 위의 증명은 건설적이지 않습니다. $M{\displaystyle }$ ${\displaystyle M}$이 알려져 있더라도 NP에서 주어진 문제의 멤버쉽을 보면 변환을 효과적으로 계산할 수 없습니다. $M{\displaystyle }$ ${\displaystyle M$의 시간 복잡도의 상한 $p{\displaystyle (n)}$ ${\displaystyle p(n)}$도 알려져 있지 않는 한.

복잡성

While the above method encodes a non-deterministic Turing machine in complexity ${\displaystyle O(\log(p(n))p(n)^{3})}$, the literature describes more sophisticated approaches in complexity ${\displaystyle O(p(n)\log(p(n)))}$.^{[8][9][10][11][12]} 준선형 결과는 쿡의 최초 발표 후 7년 후에 처음 나타났습니다.

NP-완전 문제의 존재를 증명하기 위해 SAT를 사용하는 것은 논리의 다른 계산 문제와 다른 복잡성 클래스의 완전성으로 확장될 수 있습니다. 정량화된 부울 공식 문제(QBF)는 변수에 대한 중첩된 보편적 정량화기 및 실존적 정량화기를 포함하도록 확장된 부울 공식을 포함합니다. QBF 문제는 다항식 공간 복잡도로 제한된 튜링 기계로 계산을 인코딩하는 데 사용될 수 있으며, PSPACE-완전한 문제(진정한 정량화된 부울 공식의 인식)가 있음을 증명합니다. 유사하게 의존성 정량 부울 공식은 로그 공간 복잡성으로 제한된 튜링 기계로 계산을 인코딩하여 NL-완전한 문제가 있음을 증명합니다.^[13][14]

결과들

이 증명은 NP의 모든 문제를 다항식 시간(사실은 로그 공간으로 충분함)에서 부울 만족도 문제의 예로 줄일 수 있음을 보여줍니다. 이것은 부울 만족도 문제가 결정론적 튜링 기계에 의해 다항 시간에 해결될 수 있다면 NP의 모든 문제는 다항 시간에 해결될 수 있으며 따라서 복잡도 클래스 NP는 복잡도 클래스 P와 동일하다는 것을 의미합니다.

NP-완전성의 중요성은 1972년 리처드 카프(Richard Karp)의 랜드마크 논문인 "조합적 문제들 사이의 축소성"(Recreducibility of Combinatory problem)의 출판을 통해 명확해졌으며, 그는 각각 난치성으로 악명 높은 21개의 다양한 조합적 문제와 그래프 이론적 문제가 NP-완전성임을 보여주었습니다.^[2]

Karp는 다른 문제(이미 NP-완전한 것으로 나타남)를 그 문제로 축소함으로써 그의 각각의 문제가 NP-완전하다는 것을 보여주었습니다. 예를 들어, 그는 SAT의 인스턴스를 (다항 시간에) 3SAT의 동일한 인스턴스로 줄이는 방법을 보여줌으로써 문제 3SAT(절당 변수의 음수 또는 정확히 3개의 변수가 있는 CNF(연결 정규 형태의 표현식에 대한 부울 만족도 문제)가 NP-완전임을 보여주었습니다.^[15]

게리와 존슨은 그들의 책 컴퓨터와 난치성: NP-완전성 이론에 대한 안내서에서 300개 이상의 NP-완전성 문제를 제시했고,^[16] 새로운 문제들은 여전히 그 복잡성 등급 내에 있는 것으로 발견되고 있습니다.

SAT의 많은 실제적인 예는 휴리스틱 방법으로 해결할 수 있지만, SAT에 대한 결정론적 다항 시간 알고리즘(그리고 결과적으로 다른 모든 NP-완전 문제)이 있는지에 대한 문제는 복잡성 이론가, 수학 논리학자 등의 수십 년 간의 치열한 노력에도 불구하고 여전히 유명한 해결되지 않은 문제입니다. 자세한 내용은 P 대 NP 문제를 참조하십시오.

참고문헌