[Algorithm] NP-completeness

다항 시간 내에 해결이 가능한 polynomial-time algorithm이 있다면 당연히 그렇지 못한 문제들도 있지 않겠는가? 오늘은 컴퓨터공학 전공자라면 반드시 알아야 할 NP problem에 대해 알아보자.

 

NP-completeness

 

우리가 이때까지 배웠던 거의 대부분의 알고리즘은 다항시간 내에 해결이 가능하다. input size가 n이라면 이 알고리즘의 시간 복잡도는 어떤 상수 k에 대해 $O(n^k)$라는 소리. 그렇다면 모든 문제들이 다항 시간 내에 해결이 가능한가? 정답은 No (라고 대부분의 사람들이 믿는다.) 대표적인 예로는 튜링의 Halting Problem인데 이는 어떤 컴퓨터로도, 얼마나 오랜 시간을 들이더라도 해결할 수 없다.

 

Turing's halting problem

 

Proposition) 주어진 프로그램과 입력이 있을 때, 이 프로그램이 실행을 멈출 것인지 아니면 무한히 실행될 것인지를 결정할 수 있는 알고리즘이 존재하는가?

 

Proof)

def H(P, i):
	if P(i) halts:
    	return HALT
    else:
    	return NO-HALT

어떤 결정 알고리즘 $H$가 존재한다고 가정한다. 이 알고리즘은 프로그램과 그 프로그램의 입력인 $P,i$를 입력으로 받아서 정지하면 '정지한다'라고, 그렇지 않으면 '정지하지 않는다'라고 반환한다.

def Q(X):
	if H(X, X) == HALT:
    	run forever
    else:
    	return

Q(Q) # 실행

어떤 프로그램 $Q$가 존재한다. 자신의 소스 코드를 입력으로 받는 실행을 해본다. 이제 결정 알고리즘을 실행시켜 보자.

 

$$H(Q,Q)$$

 

Contradiction)

만약 $H(Q,Q)$가 HALT를 반환한다면, Q는 무한 루프에 빠진다. 즉 정지하지 않는다. 그러나 정지한다고 했기 때문에 모순이 발생한다. 만약 NO-HALT를 반환한다면, Q는 즉시 정지한다. 그러나 정지하지 않는다고 얘기했기 때문에 모순이 발생한다.

 

언뜻 보기에는 말장난 같아 보이지만, 이를 통해 우리는 어떤 프로그램이 어떤 입력을 받았을 때 정지하는지, 하지 않는지 알 수 있는 알고리즘을 만들 수 없다는 것을 알 수 있다.

 

NP-complete

 

NP-complete 문제들의 특징은 뭐가 있을까?

 

1. 이 문제들의 status는 알려지지 않았다. 즉, 기준이 없다.

2. 다항 시간 내에 풀 수 있는 알고리즘이 아직 발견되지 않았다.

3. 다항 시간 내에 풀 수 있는 알고리즘이 존재하지 않는다는 것을 증명한 사람이 없다.

 

그래서 $P\ne NP$라는 거야? 이것은 이론 컴퓨터 과학 분야에서 가장 당혹스러운 연구 주제 중 하나이다. 아직은 알 수 없다는 소리.

 

 

Examples

몇몇의 NP-complete 문제들은 다항 시간 내에 풀 수 있는 알고리즘과 매우 비슷하게 생겼기도 하다. 몇 가지 예들을 살펴보자.

 

Shortest (tractable) vs. Longest simple paths (intractable)

 

최단 경로 알고리즘은 $O(VE)$의 시간 복잡도 내에 해결이 가능하다. 그렇다면 최장 경로 알고리즘 또한 마찬가지일까? 그렇지 않다. 자세히는 나중에 다루겠지만, 그중 한 가지 예시는 사이클이 있는 그래프는 경로가 무한히 증가함을 알 수 있다.

 

Euler tour (tractable) vs. Hamilton cycle (tractable)

 

Euler tour는 모든 간선 (edge)를 한 번씩 지나고 모든 정점 (vertex)을 한 번 이상 지나면서 사이클을 형성하는 사이클을 의미한다. 우리는 어떤 그래프가 Euler tour을 가지고 있는지 $O(E)$ 시간 내에 판단할 수 있다.

 

Hamiltonian cyle은 반대로 모든 정점을 한 번씩 지나는 사이클을 의미한다. 우리는 어떤 그래프가 Hamiltonian cycle을 가지고 있는지 다항 시간 내에 판단할 수 없다.

 

P, NP, NP-complete

 

알고리즘의 분류 중 NP와 NP-complete는 구분하기 헷갈린다. 한번 구분해 보자.

 

P

 

이 범주 안에는 다항 시간 내에 해결할 수 있는 문제들이 들어 있다. 어떤 상수 k에 대해 $O(n^k)$의 시간 내에 해결할 수 있고, 우리가 알고 공부해 온 대부분의 문제들은 이에 해당된다.

 

NP (Nondeterministic Polynomial time)

 

이 범주 안에는 다항 시간 내에 증명할 수 있는 문제들이 들어 있다. 증명할 수 있는? 이게 무슨 의미일까. 어떤 알고리즘에 대한 해답이 주어졌을 때, 이 해답이 다항 시간 내에 맞다는 것을 증명할 수 있는 문제를 의미한다. 말이 좀 복잡하다. 쉽게 말해 어떤 알고리즘의 정답을 구하는 것이 아니라, 정답이 주어졌을 때 그것의 correctness를 다항 시간 내에 판단할 수 있는지 (Yes or No)만을 보는 것이다.

 

이렇듯 P는 어떤 문제의 해답과 그것에 대항 증명을 다항 시간 내에 해결할 수 있고, NP는 해답은 알 수 없지만 해답이 주어졌을 때 그것에 대한 증명을 다항 시간 내에 해결할 수 있음을 의미한다.

$P\subseteq NP$

 

NP-complete

 

만약 어떤 문제가 NP에 포함되고, 다른 어떤 NP 문제만큼이나 '어렵다'면, 우리는 이를 NP-complete라고 칭한다. 만약 NP-complete 문제라도 다항 시간 내에 풀게 된다면, 모든 NP 문제를 다항 시간 내에 풀 수 있다고 알려져 있다. '어렵다'는 글의 자세한 의미는 나중에 더 자세히 다룰 예정이다.

 

대부분의 컴퓨터 과학자들은 NP-complete 문제들이 intractable (다루기 힘든) 하다고 믿는다. 어떤 NP-complete문제도 아직 해결되지 않았으며, 만약 해결된다면 컴퓨터 분야의 노벨상인 Turing awards를 수상할 정도라고 하니 말이다. 그렇다고 해서 우리는 NP-complete 문제가 다항 시간 내에 풀 수 있다는 가능성을 배제해서는 안된다.

 

어떤 문제를 해결하려 할 때 풀리면 풀고, 아니면 마는 거지 이렇게 복잡하게 구분하는 이유는 무엇일까? 그것은 바로 어떤 문제가 어느 범주 안에 해당하는지를 안다면 알고리즘 해결의 방향을 바꾸던가 (approximation algorithm), 혹은 쓸데없는 시간 낭비를 줄일 수 있기 때문이다. 심지어 대부분의 일상의 문제들은 오히려 NP-complete에 가까우며, 우리가 알고리즘을 통해 해결할 수 있는 매우 소수에 불과함을 간과해서는 안된다.

 

How to show a problem to be NP-complete

 

1. Decision problems vs. optimization problems

2. Reduction

3. First NP-complete problem

 

Decision problems vs. optimization problems

 

어떤 문제가 NP-complete인지는 어떻게 알 수 있을까? 대부분의 문제들은 최적화 문제이다. 주어진 상황에서 최선의 결과가 무엇인지를 판단하고 싶어 한다. 그러나 NP-complete 문제는 최적화 문제가 아니다. 그 정답이 옳고 그른지를 판단하는 결정 문제이다. 우리는 최적화 문제를 결정 문제로 변경할 수 있다.

 

최단 경로 문제에서 주어진 k에 대해 u에서 v로의 최단 경로가 k를 넘는가?

 

우리는 해당 문제를 1. 먼저 최적화 문제의 해답을 찾고, 2. 이어서 그 경로에서의 edge 개수를 세어 k와 비교함으로써 해결할 수 있다. 당연하게도 만약 최적화 문제가 쉽다면, 결정 문제도 쉬울 것이다. 이 명제의 대우로 결정 문제가 어렵다면, 최적화 문제도 어려울 것이다. 그러므로 NP-complete 문제는 최적화 문제의 함축적 의미를 가지고 있다. (최적화 문제와 관련이 있다)

 

Reduction

어떤 문제가 다른 문제보다 어렵지 않다 (혹은 쉽지 않다)는 것을 두 문제가 모두 결정 문제일 때에도 적용할 수 있다. 우리는 NP-Completeness 문제 판별을 위해 이 아이디어를 모든 NP-completeness 문제에 사용할 수 있다.

 

이에 앞서 인스턴스 (instance)란 무엇일까? 특정 문제에 들어가는 입력을 의미한다. 예를 들어 최단 경로 문제 A에선 그래프, 시작 노드, 끝 노드, 그리고 (결정 문제라면) 기준 k까지 인스턴스라고 볼 수 있다.

 

다항 시간 내에 해결할 수 있는 최단 경로 문제 B를 우리가 알고 있다고 가정하자. 이때  A의 인스턴스가 B의 인스턴스로 다항 시간 내에 변경할 수 있다면 우리는 A 또한 다항 시간 내에 해결할 수 있다고 판단 가능하다. 이때 그렇게 되도록 인스턴스를 변환해 주는 과정을 Reduction이라고 한다. 우리는 Reduction을 통해 A라는 문제를 B로 reduce 할 수 있다.

First NP-complete problem

Reduction을 통해 어떤 문제가 NP-Completeness 인지는 알 수 있지만, 이는 결국 다른 NP-Completeness 문제가 있어야지 그 문제에서 파생될 수 있는 결과이다. 그렇다면 태초의 NP-Completeness 문제는 어떻게 보이고 증명할 수 있을까? 이에 대한 해결책은 다음에 이어서 다뤄보도록 하겠다. 대표적인 First NP-complete problem에는 circuit-satisfiability problem이 있다.