[계산이론] #13. NP-Complete

2023-2학기/계산이론

[계산이론] #13. NP-Complete

AlriC 2023. 11. 29. 18:50

NP-Complete란?

지난 글에서 $\textbf{P}$는 $\textbf{NP}$에서 가장 쉬운 언어들의 집합임을 보았습니다. 이번에는 반대로 $\textbf{NP}$에서 가장 어려운 언어들의 집합인 $\textbf{NP-complete}$에 대해 알아보겠습니다.

만약 $\textbf{P}=\textbf{NP}$일 경우, $\textbf{P}$와 $\textbf{NP}$, $\textbf{NP-complete}$는 전부 동치입니다. 만약 $\textbf{P}\neq \textbf{NP}$일 경우, $\textbf{P}$와 $\textbf{NP-complete}$는 서로 Disjoint (공통된 원소가 없음) 입니다.

그림으로 정리하면 이런 느낌이겠죠.

어떤 Language $B$가 아래 조건을 만족하면 우리는 $B$를 $\textbf{NP-complete}$라고 부릅니다.

$B \in \textbf{NP}$
$\forall A\in \textbf{NP}, A\leq _PB$

이를 이용해, 만약 어떤 언어가 $\textbf{NP-complete}$이면 아래가 성립합니다.

$$B\in \textbf{P}\Leftrightarrow \textbf{P}=\textbf{NP}$$

당연한 거죠. 어떤 언어가 $\textbf{P}$라면 그 언어는 $\textbf{NP}$에서 가장 쉬운 언어라는 것인데, 그 언어가 $\textbf{NP}$에서 가장 어렵기도 하다는 뜻이니깐요.

3SAT 문제

어떤 언어 $C$가 $\textbf{NP-complete}$임을 보이기 위해서 보편적으로 사용하는 방법은, $\textbf{NP}$임이 증명된 다른 언어 $B$를 잡은 뒤에 $B\leq_PC$임을 보이는 것입니다.

나중에 증명하겠지만, 3SAT 문제는 $\textbf{NP-complete}$입니다. 이를 직접 증명하기 위해서는 $\textbf{NP}$에 속하는 모든 언어 $A$에 대해 $A\leq_P 3SAT$임을 증명해야 합니다. 하지만 그러기는 쉽지 않죠. 그래서 저희는 $3SAT$보다 쉬우면서, $\textbf{NP-complete}$인 언어를 통해 $3SAT \in \textbf{NP-complete}$임을 보이도록 하겠습니다.

(이번 글은 $SAT$보다 쉬우면서 $\textbf{NP-complete}$인 언어에 대해 다루고, 실제로 $3SAT$가 $\textbf{NP-complete}$임을 증명하는 과정은 다음 글에서 다루겠습니다.)

도미노 문제

이렇게 생긴 타일들이 있습니다. 모든 타일은 4개의 부분으로 나뉘어 있으며 각 부분에는 색이 칠해져 있습니다. (보기 좋으라고 색으로 표시해 둔 것이지 나중에는 빨간색, 주황색, 초록색 대신 1, 2, 3과 같은 숫자 라벨을 사용합니다.) 저희의 목표는 이 타일들만을 사용하여 아래의 칸에 타일들을 채우는 것입니다. 한 종류의 타일을 여러 번 사용해도 괜찮으며, 그 횟수에는 제한이 없습니다.

저희가 타일을 채워야 할 칸은 $t \times t$개이며, 프레임에 둘러싸여 있습니다. $t$개의 칸으로 이루어진 프레임이 총 4개 존재하며, 각 칸은 각자의 색을 가지고 있습니다. (각자의 라벨을 가지고 있습니다.)

여기서 타일을 채울 때의 규칙은, 서로 인접한 부분에는 같은 색이 칠해져있어야 합니다. (같은 라벨이 붙어있어야 합니다.) 이 규칙에 맞게 타일을 채우면 아래와 같은 모습입니다.

이렇게 모든 칸에 타일을 채울 수 있다면, 이 도미노는 Solvable 하다고 부릅니다.

이를 조금 수학적으로 표현해 보겠습니다. 먼저 각 색(라벨)은 길이가 $m$이고 알파벳이 $\Sigma =\left\{0,1 \right\}^m$인 이진 문자열로 표현됩니다. 빨간색은 0000, 주황색은 0001, 뭐 이런 식이겠죠.

그리고 타일의 타입은 총 4개의 라벨을 포함해야 하므로 $\Sigma^4$의 원소인 4비트 문자열의 tuple로 나타내질 수 있습니다. 프레임의 경우 하나당 $t$개의 라벨을 포함하고, 이 프레임이 총 4개가 필요하므로 $\Sigma^{4t}$의 원소로 표현할 수 있습니다. 이를 이용한 언어 $Domino$는 아래와 같이 정의됩니다.

$$Domino=\left\{\left<m, k, t, R, T_1, \cdots, T_k \right>: \\ m, k, t\geq 1, R\in \Sigma^{4t}, T_i\in \Sigma^{4}, 1\leq i\leq k, \\ R\ can\ be\ filled\ with\ T_is \right\}$$

여기서 $m$은 라벨을 나타내는 문자열의 길이, $k$는 타일 종류의 개수, $t$는 프레임의 길이, $R$은 프레임, $T_i$는 타일의 종류를 의미합니다.

도미노 게임의 NP-Completeness

이렇게 정의된 $Domino$는 $\textbf{NP-complete}$입니다.

이를 증명하기 위한 첫 단계는 바로 $Domino$가 $\textbf{NP}$임을 증명하는 것입니다. 이는 간단합니다. 도미노와 이 도미노에 대한 Soultion이 주어졌을 때, 그냥 타일의 모든 접합부에서 같은 라벨을 가진 부분이 만났는지를 확인하면 Soultion에 대한 판단이 이루어집니다. 이 과정은 Polynomial Time에 가능하고요.

그다음으로는, 모든 NP 문제들이 Domino로 치환될 수 있음을 보일 겁니다. 그러면 자연스럽게 모든 NP 문제들은 Domino 문제보다 더 쉬운 문제가 되므로, Domino는 NP-complete임이 증명됩니다. 그전에, Lemma 하나를 보고 넘어갑시다.

$\textbf{NP}$에 속하는 모든 언어는 아래 조건을 만족하는 Non-Deterministic TM $N$에 의해 Polynomial Time에 Decide 될 수 있습니다.

Computation 동안, $N$의 Head는 시작한 Cell의 왼쪽으로 넘어가지 않습니다.
Computation이 끝났을 때, $N$에는 시작한 Cell에 적힌 문자밖에 남아있지 않습니다.
Head가 움직이는 방향은 $N$의 State에 의해서만 결정됩니다. 즉, State가 같으면 Head의 방향도 같습니다.

이에 대한 증명은 따로 하지 않겠습니다.

이제 임의의 $\textbf{NP}$ 언어인 $A$가 있다고 가정합시다. 그러면 위 Lemma에 의해 이 언어를 Polynomial Time $p$에 해결하며 위 세 조건을 만족하는 Turing Machine $M$이 존재하겠죠.

저희의 목표는 Turing Machine $M$과 입력한 문자열 $w$를 받아 도미노 게임을 만드는 건데, 어떻게 만드냐. $M$이 $w$를Accept 하는 경우 이 도미노 게임이 Solvable, $w$를 Reject 하는 경우 이 도미노 게임이 Non-Solvable 하도록 도미노 게임을 만드는 것입니다.

그러면 임의의 $\textbf{NP}$ 언어 $A$가 도미노 게임으로 변환될 수 있음이 증명되고, 도미노 게임은 모든 $\textbf{NP}$ 언어보다 어렵다는 것이 증명되므로 도미노 게임이 $\textbf{NP-complete}$임이 증명되는 것입니다.

기본적인 아이디어는 아래와 같이 시작합니다. 먼저 $M$이 $A$를 Decide 하는 데에 $p$의 시간이 필요하다고 했으므로, 최대 필요한 Computation Step의 개수는 $p\left( n \right)$입니다. 그리고 Head는 시작한 Cell 왼쪽으로 넘어가지 않기 때문에, 최대한으로 필요한 Cell의 개수도 $p\left( n \right)$입니다.

이에 착안해서 $p\left( n \right) \times p\left( n \right)$ 프레임의 도미노 게임을 설계합니다. 그리고 각 행은 하나의 Computation Step을 의미하고, 각 행에서 각 타일들은 Turing Machine의 Cell을 의미합니다.

이해를 돕기 위해 간단한 예시를 하나 보고 가겠습니다. $z_00 \to z_21R,\; z_21\rightarrow z30N$ 이렇게 두 Instcution이 실행되는 동안, Turing Machine에서는 아래와 같은 일이 일어납니다.

그리고 이 과정을 도미노 게임으로 옮기면 아래와 같습니다.

이렇게 각 타일의 위쪽, 아래쪽 부분은 Computation Step이 일어나기 전과 후의 상태와 Cell에 저장된 값을 의미합니다. 그리고 좌우에 있는 부분은 다음 Step에 Head가 어느 방향으로 넘어갈지, 그리고 어느 방향에서 Head가 넘어왔는지를 의미합니다.

이를 위해 아래와 같이 타일 타입을 정의합니다.

먼저 $M$에 존재하는 모든 Symbol $a$에 대해 위와 같이 생긴 타일 타입을 만들어줍니다. 이 타일은 Head의 영향을 받지 않는 부분들에 채워져 있습니다.

그리고 Instrcution $ za\rightarrow z'bR $에 대해, 위와 같은 타일 타입을 만듭니다. Computation Step 이전, Head는 이 Cell 위에 존재하며 Computation Step 이후에 Head는 오른쪽으로 이동합니다.

반대로 $ za\rightarrow z'bL $에 대해서는 위와 같은 타일 타입을 만듭니다. 아까 전에 봤던 타일과 기능은 같지만, Head가 다음 Step에 왼쪽으로 이동한다는 사실을 표현하고 있습니다.

마찬가지로 \$ za\rightarrow z'bN $에 대해서는 위와 같은 타일 타입을 만듭니다. 역시 위 두 타일과 같은 기능을 하는 타일이지만 Head가 다음 Step에 움직이지 않는다는 사실을 나타내 줍니다.

그리고 각 State $z$와 각 Symbol $a$에 대해 위와 같은 타일 타입 2개 만듭니다. 이 타일은 각각 Head가 Cell의 왼쪽에서 넘어왔는지, 오른쪽에서 넘어왔는지를 알려줍니다.

예시를 통해 Turing Machine의 동작을 도미노 게임으로 변환하는 과정을 더 자세히 알아보겠습니다. 어떤 이진수를 받아 그 이진수에 1을 더하는 TM을 하나 생각합시다. 편의상, Input은 항상 0으로 시작한다고 가정하겠습니다. 이 TM은 아래와 같은 알고리즘으로 작동합니다.

procedure Successor(x)
	move to the last symbol
	while a '1' is read do
		replace this '1' with a '0'
		move one position to the left
	replace the '0' beight read with a '1'

예시로 431, 2진수로 110101111을 집어넣으면 이 TM은 가장 오른쪽으로 먼저 이동한 뒤, 1이 나오지 않을 때까지 왼쪽으로 한 칸씩 이동하면서 1을 0으로 바꿉니다. 그리고 0이 나오면 그 0을 1로 바꿉니다.