[알고리즘] P와 NP

 

 

 

 

🧐 Problem

이전 글에서 살펴보았던 problem에 관련한 개념들을 다시 살펴보도록 하겠습니다.

Problem Instance : 어떤 문제(problem)를 정의하는 input이며, 이때 해당 input을 일종의 binary string으로 생각할 수 있습니다.

Problem : 어떤 조건을 만족시키는(YES라 답하는) problem instance들의 집합을 의미합니다.

이때 Problem에 속하는 instance들을 YES instance라 합니다.

Algorithm : 어떤 problem X에 대하여,
어떤 mapping 함수 A가 임의의 s $\in $ X에 대하여 A(s) = YES이고,
역( A(s) = YES일 경우 s $\in$ X )도 성립하는 경우 A를 problem X를 해결하는 Algorithm이라고 합니다. 

 

 

 

 

 

 

 

 

 

 

🧐 Polynomial Running Time Algorithm

임의의 input(string) s에 대해서, A(s)가 최대 O( poly( |s| ) ) 단계 안에 종료되는 경우,
Algorithm A는 polynomial running time을 가지고 있다고 합니다.

예를 들어 버블정렬, 퀵정렬 등의 정렬 알고리즘은 최악의 시간복잡도로 $O(n^2)$ 을 가집니다.

즉 이들은 Polynomial Time Algorithm입니다.

 

 

 

 

 

 

 

 

 

🧐 P(Polynomial Time)

이제 P에 대하여 정의해 보도록 하겠습니다.

P(Polynomial time) : polynomial running time을 가진 algorithm이 존재하는 모든 decision problem들의 집합을 의미합니다.

예를 들어 다음과 같은 결정 문제들이 P에 속하는 문제들입니다.

• 정점이 n개인 그래프에서, Shortest Path의 길이가 k 이상인 두 정점 u, v가 존재하는가?
• 정점이 n개, edge가 m개인 그래프의 biconnected component는 k개 이상 존재하는가?
• 길이가 n인 sequence의 LIS의 길이가 k 이상인가?

 

 

그에 반하여, 이전 글에서  살펴본 Independent Sets, Cliques, Vertex Cover, 3-SAT 문제들은 P 문제가 아닙니다.

 

즉 해당 문제들을 polynomial runnong time에 해결하는 알고리즘이 존재하는지 모릅니다.

 

위와 같은 문제들은 수없이 많이 존재하는데, 저희는`위와 같은 문제들`의 공통적인 특징에 집중하여 이들을 formal하게 정의해보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Certifiers

위에서 언급된 문제들의 공통적인 특징은 다음과 같습니다.

 

Problem X에 속한 instance $I_X$ 에 대하여, 해당 $I_X$ 가 실제로 YES Instance인지 확인할 수 있는 poly( |$I_X$| )의 길이를 가지는 proof/certificate/solution이 존재합니다.

 

간단한 2-SAT문제를 통해 예시를 살펴보도록 하겠습니다.

 

 

 

 

 

이제 이를 통해 Certifier에 대한 정의를 살펴보도록 하겠습니다.

어떤 Problem X와 input(string) s 대하여, 

1) s $\in$ X 이면 C(s, t) = YES를 만족시키는 string t가 존재하고,
2) 반대로 어떤 s와 t에 대하여, C(s, t) = YES 이면 s $\in$ X이다.

1), 2)를 만족시키는 알고리즘 C를 problem X의 certifier라고 합니다.
이 때 string t는 s의 certificate(혹은 proof)라고 합니다.

이때 특별히 모든 string s에 대하여,

1) s $\in$ X  if and only if |t|  $\leq$ poly(|s|) 이면서, C(s, t) = YES를 만족시키는 t가 존재한다.
2) Polynomial time 안에 답을 낼 수 있다.

1), 2) 를 만족하는 Certifier C가 존재하는 경우 C를 efficient certifier라고 합니다.

 

조금의 이해를 돕기 위해, 어떤 어려운 문제를 풀려고 도전하는 저와, 제 3자 두명([1], [2]로 하겠습니다.)를 추가하여 설명해 보도록 하겠습니다.

 

제가 문제를 풀려도 계속 시도하였으나, 문제가 풀리지 않아 끙끙대고 있었다고 생각해 보겠습니다.

이때 [1]이 저한테 와서, 이게 답인거 같은데 한번 확인해 줄 수 있어? 라고 하며 종이를 하나 줍니다.

 

저는 해당 종이에 적힌 것이 답인지를 확인하기 위해 어떠한 과정을 거쳐서 확인해 보았고, 결국 이것이 답이 아님을 확인하였습니다.

 

이번에는 [2]가 저에게 와서 이게 답인거 같은데 한번 확인해 줄 수 있어? 라고 하며 종이를 하나 줍니다.

똑같이 해당 종이에 적힌 것이 답인지를 확인하기 위해 어떠한 과정을 거쳐서 확인해 보았고, 결국 이것이 답임을 확인하였습니다.

 

그렇지만, 여전히 답을 어떻게 구했는지는 모르는 상황입니다.

 

 

위와 같은 상황에서, [2]가 저에게 준 답이 certificate가 되는 것이고,

([1]이 준 답은 certificate가 아님)

 

제가 종이를 받아 답인지 확인하는 과정(알고리즘)을 Certifier라고 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Certifiers 예시 - Independent Set

Problem : 어떤 그래프 G = (V, E) 가 크기 k 이상인 independent set을 포함하는가?

Certificate : 어떠한 집합 S (S $\subset$ V)

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

여기서 instance는 어떤 그래프인 G와, k가 됩니다.

 

 

 

 

 

 

🧐 Certifiers 예시 - Vertex Cover

Problem : 어떤 그래프 G = (V, E) 가 크기 k 이하인 vertex cover을 포함하는가?

Certificate : 어떠한 집합 S (S $\subset$ V)

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

 

 

 

 

 

🧐 Certifiers 예시 - 3-SAT

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

Certificate : F의 각각의 variable에 0 또는 1을 assign 한 것

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

 

 

 

 

 

 

 

 

 

🧐 Nondeterministic Polynomial Time (NP)

Nondeterministic Polynomial Time(NP)는 efficient certifier를 가진 모든 problem들의 집합입니다.

앞서 살펴본 Independent Set, Vertex Cover, 3-SAT은 모두 NP에 속합니다.

(이들의 certifier가 모두 efficient certifier가 됨을 쉽게 증명할 수 있습니다.)

 

조금 더 formal한 정의는 다음과 같습니다.

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

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

2. s가 NO Instance라면, 즉 s $\notin$ X, 모든 string t에 대해 C(s, t) = NO 라 답한다.

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

 

 

 

 

 

 

 

 

🧐 Independent Set이 NP인 이유

Independent Set Problem의 어떤 instance s(즉 G와 k)에 대하여, 

어떤 certificate t와, certifier C(s, t)를 각각 다음과 같이 정의하겠습니다.

Certificate : 어떠한 YES Instance 집합 S (S $\subset$ V) (즉 정답 집합)

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

그러면 certificate는 |s| 보다 작기 때문에 |s| 에 대한 polynomial로 표현되는 것을 알 수 있습니다.

 

s가 YES instance인 경우, C(s, t) = YES인 certificate t가 존재한다는 것은 문제의 정의에 의하여 자명합니다.

(s가 NO instance라면, 모든 string t'에 대하여 C(s, t')은 NO를 return합니다.)

 

마지막으로 C(s, t)는 t에 속한 정점들의 각 pair(u, v)에 대하여, u, v,가 adjacent한지 O(1) 시간에 검증 가능하므로, 총 O(| $t^2$ |) 시간이 소모됩니다. 따라서 C(s, t)는 efficient certifier입니다.

 

따라서 Independent Set은 efficient certifier를 가지므로 정의에 의하여 NP에 속합니다.

 

 

 

 

 

 

 

 

🧐 NP의 정의와 관련된 주의사항

NP의 정의는 오로지 YES instance 만이 크기가 작은 proof/certificate를 가진다는 것을 의미합니다.

이는 NO instance의 경우에 대해서는 적용되지 않습니다.

 

이러한 문제를 정의하기 위해 co-NP 라는 problem class가 따로 존재합니다.

 

 

 

 

 

 

 

 

🧐 P $\subseteq$ NP 증명

P에 속한 어떤 problem X와,

X를 해결하는 polynomial time algorithm A가 있다고 하겠습니다.

 

이제 해당 X가 efficient certifier를 가지고 있음을 증명하면 P $\subseteq$ NP임을 증명할 수 있습니다.

 

 

어떤 문제를 해결하는 algorithm 이 있으면 (해당 algorithm 이 certifier 의 역할을 할 수 있으므로) certifier 를 쉽게 디자인 할 수 있습니다.

 

Certifier C(s, t)를 A(s)를 실행한 후 나오는 대답이라고 하겠습니다.

그러면 정의에 의하여 A는 polynomial time에 동작하므로 C 역시 polynomial time에 동작합니다.

 

certifier가 되기 위해서는 다음을 만족해야 합니다.

1) s $\in$ X 이면 C(s, t) = YES를 만족시키는 string t가 존재하고,
2) 반대로 어떤 s와 t에 대하여, C(s, t) = YES 이면 s $\in$ X이다.

Case 1:  s $\in$ X인 경우 : 모든 t에 대해서 YES를 출력하므로, t가 반드시 존재합니다.

Case 2: s $\notin $ X 인 경우 : 모든 t에 대해서 NO를 출력합니다.

 

 

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

 

 

 

 

 

 

 

 

 

 

 

🧐 EXP (Exponential Time)

EXP(Exponential Time)은 input s에 대하여, O($2^{poly(|s|)}$) 시간 안에 해결 가능한 모든 문제들의 집합입니다.

예를 들어 O($2^n$), O($3^n$) 등이 있습니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 NP $\subseteq$ EXP 증명

NP에 속한 어떤 problem X를 해결하는 다음과 같은 exponential algorithm을 디자인하면 됩니다.

 

Algorithm: t = O( p(|s|) )를 만족하는 모든 t에 대하여, C(s, t)를 수행한 후, 이 중 한 번 이상 certifier C가 YES를 return한 경우, YES를 return합니다.