[Algorithm] NP-Complete (NP-완전)

저번에 다룬 Problem 개념을 재정의하겠습니다.

 

Problem Instance 는 일종의 binary string 이라고 생각할 수 있습니다. (Instance 가 Binary Code로 전환되었다고 생각합시다.)

 

Problem 을 다음과 같이 재정의하도록 하겠습니다.

Problem : 어떤 조건을 만족시키는 ( = YES 라 답하는 ) Problem Instance 들의 set. 그러므로, Problem 에 속한 Instance 는 모두 YES Instance가 됩니다.

 

어떤 Problem X 에 대해 어떤 mapping A 가 임의의 s ∈ X 에 대해 A(s) = YES이고, 역도 성립할 경우 A를 Problem X를 해결하는 Alogrithm 이라고 합니다.

 

이제 NP - Completeness 를 이해하기 위한 개념들을 하나씩 살펴보도록 하겠습니다.

 

먼저 알아야할 개념은 P(Polynomial Time)입니다.

Definition of P(Polynomial Time) : Polynomial Time(P) 는 polynomial running time 을 가진 algorithm 이 존재하는 모든 (Decision) Problem 들의 집합입니다.

 

Polynomial Running Time 이란? : 임의의 string s 에 대해, A(s) 가 최대 O(poly|s|) 안에 답을 낼 수 있는 경우, Algorithm A 는 Polynomial Running Time 을 가지고 있다고 이야기합니다.

 

이전 Reduction 관련 포스팅에서 다룬 Independent Set Problem, Cilque Problem, Vertex Cover Problem, 3-SAT Problem 들은 P에 속하는 문제들인지 모릅니다. 즉, 저 문제들을 해결하는 Polynomial Running Time Algorithm 을 모릅니다. 이 문제들 이외에도 P에 속하는 지 아닌 지 알 수 없는 알고리즘은 수없이 많이 존재합니다. 이런 문제들은 어떠한 공통적인 특징들을 가지고 있는지 살펴보겠습니다.

 

앞서 언급한 Problem 들의 공통적인 특징은 다음과 같습니다.

Problem X 에 속한 Instance Ix 에 대해서 이 Ix가 실제로 YES Instance 인지 확인할 수 있는 poly(Ix|) 크기의 proof(증명), solution(해) 가 존재합니다. 이러한 proof 나 solution 등을 Certificate 라고 합니다. 예시를 살펴보겠습니다.

X1 = T, X2 = T는 Ix 의 Proof 이자 Ix 의 Certificate

 

다음으로, Certifier 의 개념에 대해 알아보도록 하겠습니다.

Definition of Certifier
어떤 Problem X 에 대해 1. s ∈ X 이면 C(s,t) = YES 를 만족시키는 string t 가 존재하고 2. 반대로 어떤 s와 t에 대해 C(s,t) = YES 이면 s ∈ X이다. 두 조건을 만족시키는 Algorithm C 를 Problem X 의 Certifier 라고 합니다. 이 때 string t 는 s의 certificate (혹은 proof) 라고합니다.

 

이 때, 특별히 모든 string s 에 대해 1. s ∈ X <=> |t| <= poly (|s|) 이면서 C(s,t) = YES 를 만족시키는 t 가 존재하며 2. Polynomial time 안에 답을 낼 수 있는 Certifier C가 존재한다. 두 조건을 만족시키는 C를 Efficient Certifier 라고합니다.

 

예시들을 보며 Certificate와 Certifier 에 대해 이해해 보도록합시다.

 

예시 1.

Problem : 어떤 graph G = (V, E) 가 size 가 k 이상인 independent set 을 포함하는가?

1) Certificate : 어떤 set S ⊂ V

2) Certifier : |S| 가 k 이상인지 확인 후, S 에 속한 임의의 두 vertex 가 서로 adjacent 하지 않은지를 확인

 

예시 2.

Problem : 어떤 graph G = (V, E) 가 size 가 k 이하인 vertex cover 을 포함하는가?

1) Certificate : 어떤 set S ⊂ V

2) Certifier : |S| 가 k 이하인지 확인 후, G 의 모든 edge 들이 S 에 속한 vertex 들 중 적어도 하나를 포함 하는지 확인.

 

예시 3.

Problem : 어떤 3-CNF formula F s는 satisfiable 한가?

1) Certificate : F 의 각각의 variable 에 0/1 을 assign 한 것.

2) Certifier : 해당 assignment 에 대해 F 가 true 인지 판별 (F 의 모든 clause 가 true 이면 YES).

 

이제 NP 의 개념에 대해 알아보도록 하겠습니다. NP 와 NP - Complete 은 다른 것과 유의하며 살펴봅시다.

 

Definition of NP (Nondeterministic Polynomial Time)

Nondeterministic Polynomial Time (NP) 는 Efficient Certifier 를 가진 모든 Problem 들의 집합입니다.

 

예를 들어, Independent Set, Vertex Cover, 3-SAT Problem 모두 NP에 속합니다. |t| <= poly(|s|), C = O(poly|s|).

좀 더 Formal 한 정의는 다음과 같습니다.

어떤 Problem X 가 NP에 속한다면, 모든 string s 에 대해 다음을 만족하는 polynomial p와 q, certifier C 가 존재한다.

1. s가 YES Instance 라면 (즉 s ∈ X), |t| = p(|s|) 이면서 C(s,t) = YES 를 만족하는 certificate t 가 존재합니다.

2. s가 NO Instance 라면 즉 (즉 s ∉ X), 모든 string t 에 대해 C(s,t) = NO .

3. C(s,t) 는 q(|s|+|t|) = poly(|s|) 시간 안에 동작한다.

다음의 예시를 통해 어떤 Problem 이 NP 임을 증명하는 법을 알아보도록 합시다.

Independent Set 이 NP임을 증명

 

이번에는 P와 NP의 관게에 대해서 알아보도록 하겠습니다.  P와 NP 사이에는 다음과 같은 관계가 성립합니다.

 

P ⊆ NP

 

Proof : P에 속한 어떤 Problem X 가 있고, 따라서 이 X를 해결하는 Polynomial-Time Algorithm A 가 있습니다.. 이제 이 X 가 Efficient Certifier 를 가지고 있다는 것을 증명하면 됩니다.

Certifier C(s,t) 의 결과가 A(s) 의 결과라고 합시다. 그러면 정의에 의해 C는 당연히 Polynomial Time 에 동작합니다.
Case 1 : s ∈ X 인 경우, C(s, t) = YES 를 만족하는 t 가 반드시 존재.

Case 2 : s ∉ X 인 경우, 모든 t에 대해 NO 를 출력합니다.

그러므로, 정의에 의해 C는 efficient Certifier 이므로, P는 NP에 속합니다.

 

다음으로, EXP(Exponential Time) 에 대해 알아보도록 하겠습니다.

Definition of EXP : EXP 는 input s 에 대해 O(2^(poly(s|)) 시간 안에 해결 가능한 모든 문제들의 집합입니다.

 

EXP와 NP 사이에는 다음과 같은 관계가 성립합니다.

NP ⊆ EXP

Proof : NP에 속한 어떤 Problem X 를 해결하는 다음과 같은 Exponential Algorithm 을 디자인하겠습니다.
Algorithm : t = O(p(|s|)) 를 만족하는 모든 t 에 대해 C(s,t) 를 수행한 후, 이 중 한번 이상 Certifier C가 YES를 return 한 경우, YES를 return 한다. (아닐 시 NO) 이 알고리즘은 가능한 모든 경우를 다 따지므로 올바르게 해결하는 Algorithm 입니다. (Brute-Force 같은 느낌) 그리고 이 알고리즘의 동작 시간은 O(q(|s| + p(|s|)) * 2^(poly(|s|)) 입니다. 따라서 EXP의 정의에 의해 NP는 EXP에 속합니다.

 

* NP에 속하면서 P에 속하지 않은 문제에 대한 존재는 아직 밝혀지지 않았습니다!

NP에 속한 문제 중 가장 어려운 문제를 어떻게 정의할 수 있을까요? 이전 포스팅에서 Reduction 을 이용해 두 Problem 간에 더 어려운 문제를 정의했습니다. 따라서 Reduction 을 이용하여 '가장 어려운 문제' 를 정의해보겠습니다.

 

Definition of NP-Complete (NP 중 가장 어려운 문제!)

조건 1 : X ∈ NP
조건 2 (Hardness) : 어떤 Y ∈ NP 에 대해서도 Y <= pX 가 성립.
위의 두 조건이 성립할 경우 문제 X 를 NP - Complete 라고 합니다.
X가 조건 2 만을 만족하면, NP - hard 라고 합니다. 따라서 NP - Hard 는 NP - Complete 를 포함합니다. 어떤 문제가 NP-Complete 임을 보이기 위해서는 조건 1과 조건 2를 이용하면 됩니다.

 

만약 X가 NP-Complete 에 속한 Problem 일 때, "P = NP <=> X를 polynomial Time 안에 해결가능" 이 성립합니다.

(P=NP임은 밝혀지지 않았습니다.)
proof
( <- 방향 증명 ) X를 Polynomial Time 에 해결가능한 경우, NP에 속한 임의의 Y에 대해 Y <= pX 가 성립하므로, Y는 Polynomial Time 안에 해결할 수 있게됩니다. 따라서 Y 는 정의에 의해 P이므로 P = NP입니다.

( -> 방향 증명 ) X는 NP에 속해있으므로, NP = P 라면 X는 P에도 속하게 되므로 Polynomial Time 안에 해결할 수 있습니다.

대부분의 사람들은 현재 P ≠ NP 라 생각하고 있으며, 따라서 X 를 해결하는 polynomial-time algorithm 또한 없을 거라 생각하고 있습니다.

 

SUMMARY

 

Definition of P(Polynomial Time) : Polynomial Time(P) 는 polynomial running time 을 가진 algorithm 이 존재하는 모든 (Decision) Problem 들의 집합

Definition of NP (Nondeterministic Polynomial Time)

Nondeterministic Polynomial Time (NP) 는 Efficient Certifier 를 가진 모든 Problem 들의 집합

Definition of Certifier
어떤 Problem X 에 대해 1. s ∈ X 이면 C(s,t) = YES 를 만족시키는 string t 가 존재하고 2. 반대로 어떤 s와 t에 대해 C(s,t) = YES 이면 s ∈ X이다. 두 조건을 만족시키는 Algorithm C 를 Problem X 의 Certifier 라고 합니다. 이 때 string t 는 s의 certificate (혹은 proof) 라고합니다.

이 때, 특별히 모든 string s 에 대해 1. s ∈ X <=> |t| <= poly (|s|) 이면서 C(s,t) = YES 를 만족시키는 t 가 존재하며 2. Polynomial time 안에 답을 낼 수 있는 Certifier C가 존재한다. 두 조건을 만족시키는 C를 Efficient Certifier 라고합니다.

P ⊆ NP 인 이유 : 1. A(s)가 Polynomial Time 에 동작하는 C(s,t) 2. C(s,t) 는 Certifier 의 조건을 충족

NP-Complete임을 보이는 법 : Problem X가 NP이고, NP-Complete Y <= pX임을 보이면 됨.