Theory of NP

 

Computational Complexity Analysis - Sorting problem

이전에는 알고리즘이 갖는 한계를 알아봤었다.

이번에는 문제 자체가 갖는 한계를 알아보자.

(즉, 어떠한 알고리즘을 써도 이보다 낫게 풀 수 없다는 것)

 

문제의 종류는 아래의 세 종류가 있다.

1. Polynomial-Time algorithm found
   다항식의 차수 시간 복잡도를 갖는 알고리즘으로 문제를 풀 수 있는 경우.
   - Sorting
   - Shortest paths problem
   - Minimum spanning tree problem
   ...
2. Proven to be Intractable
   다항식의 차수 시간 복잡도를 갖는 알고리즘으로 풀 수 없다고 증명된 문제.
   output의 양 자체가 매우 많거나, 결정 불가능한 문제(알고리즘을 만들 수 없는 문제)가 이에 해당.
   - printing all Hamiltonian Circuits
   - printing all Permutations of n keys
   - Halting problem
   ...
3. Not Proven to be intractable, but poly.-time algorithm have never been found
   2번처럼 풀 수 없다고 증명되지는 않았지만, 그렇다고 해서 1번의 방법으로 해결된 적이 없는 문제.
   - 0-1 Knapsack problem
   - TSP
   - m-coloring problem (m>2)
   ...

 

Decision Problem

결과가 Yes 또는 No로 나오는 문제를 의미한다.

사실 위의 3번 케이스의 문제와 같이 어려운 문제를 포함한 모든 최적화 문제는

그에 대응되는 decition problem이 있다.

 

예로들어 TSP Decision problem은 다음과 같이 만들 수 있을 것이다.

특정 d를 입력으로 줄 때, 이 보다 짧은 길이의 경로가 존재하는가? 를 출력하는 문제

0-1 Knapsack problem과 같은 경우에는 이득 R보다 큰 이득을 갖는 경우가 존재하는가? 와 같이 대응할 수 있다.

 

P

Polynomial-time algorithm으로 해결할 수 있는 Decision problem의 집합을 P 문제 라고 한다.

그렇기에, TSP decision, 0-1 Knapsack decision 문제는 3번 케이스에 포함됨에 따라 P에 포함되는지 알 수 없다.

 

Nondeterministic Algorithm

동일한 input에 대해 다음 단계가 여러 상태로 결정될 수 있기 때문에

다른 output이 도출될 수 있는 알고리즘을 의미한다.

Decision problem에 대해 이 알고리즘이 내놓은 결과 중에서 무엇을 Solve라고 할 수 있을까?

 

바로 내놓은 결과가 Yes인 경우에 verification stage가 true를 반환하면 된다.

- Verification stage

입력으로 들어온 claimed solution이 실제 decision problem의 결과면 true를 반환하는 검증단계.

 

예를 들어보자.

claimed solution S에 대해 verify가 다음과 같은 output를 뱉는다면,

이 Decition problem을 푸는 Nondeterministic Algorithm이 Solve 했다고 하는 것이다.

 

Nondeterministic Algorithm 중에서 verification stage가 Polynomial-time 알고리즘으로 해결된다면,

그 알고리즘을 Polynomial-time Nondeterministic Algorithm라고 한다.

 

NP

Polynomial-time Nondeterministic Algorithm으로 해결할 수 있는 Decision problem의 집합을 NP 문제라고 한다.

여기에 포함되는 문제로는 3번 케이스의 문제들이 대응되는 Decision problem 뿐만 아니라,

모든 P 문제도 포함된다.

 

대부분의 문제는 NP 문제이고, NP에도 속하지 못하는 문제는

2번 케이스와 같이 알고리즘 자체가 없는 문제이거나,

Verification stage가 Non-Polynomial-time이 걸리는 문제가 이에 해당한다.

 

하지만 현재로서는 P가 NP의 진 부분집합인지는 아무도 모른다.

 

Transformation Algorithm

문제 A의 인스턴스를 문제 B의 인스턴스로 바꿔주는 알고리즘을 의미한다.

 

예로 들어보면,

A: 배열의 절반 앞쪽에 가장 작은 수가 존재하는가?
B: 배열의 절반 앞쪽에 가장 큰 수가 존재하는가?
Transformation Algorithm: b = -a

 

b 문제가 true가 나왔다는 것은 배열의 절반 앞쪽에 가장 큰 수가 존재한다는 뜻이고,

그 말은 -a 문제는 배열의 절반 앞쪽에 가장 큰 수가 존재한다는 뜻이 되니까,

a 문제는 배열의 절반 앞쪽에 가장 작은 수가 존재한다는 뜻이 된다.

 

NP-Complete problem

NP에 있는 특정 한 문제를 해결하는 Transformation Algorithm로 변환된 문제 P를 찾는다면,

다른 모든 NP문제도 P 문제로 변환해 해결 가능하다는 문제.

(즉, 하나만 변환 가능해도 다른 모든 문제를 변환해 풀 수 있다는 뜻)

 

NP-Complete

특정 문제 B가 NP에 속하면서, NP에 속한 아무런 상관이 없는 문제 A가

Polynomial-time의 Transformation Algorithm 알고리즘으로 문제 B로 변환될 수 있다면,

그 문제 B를 NP-Complete하다고 한다.

또한, 둘의 관계는 A reduces to B 관계라고 한다.

(또는, A is Polynomial-time reducible to B)

 

NP-Complete(이하 NPc)의 특징은, NP-Complete라고 증명된 문제 B가

B reduces to C의 관계를 갖는다면, C역시 NP-Complete 문제라는 특징이 있다.

 

P는 NP의 진 부분집합인지 아닌지 모르지만, NPc는 NP의 진 부분집합이다.

그렇기에 P와 NP의 관계에 따라 NPc 문제의 해결 가능성이 달라진다.

만약 P=NP라면, NPc는 P의 진 부분집합이라는 뜻이 되니, NPc 문제는 Polynomial-time에 해결 가능해진다.

반대로 P가 NP의 진 부분집합이라면, NPc와 P의 교집합이 없어지므로, NPc문제는 Polynomial-time에 해결 불가능해진다.

 

NP-Hard

NPc에 속한 아무런 상관이 없는 문제 A가 

Polynomial-time의 Transformation Algorithm 알고리즘으로 문제 B로 변환될 수 있다면,

문제 B를 NP-Hard 라고 한다.

이 때, 문제 B의 특징이 여럿 있다.

• B는 NP에 속할 필요가 없다.
• B는 Decision problem일 필요가 없다.
• B를 해결하는 알고리즘이 꼭 존재할 필요가 없다.

 

만약, Polynomial-time에 특정 NP-Hard문제를 해결할 수 있는 알고리즘이 발견된다면,

P=NP 관계가 증명된다.