[방법론] P, NP, NP-Complete, NP-Hard

알고리즘을 공부하기 앞서 알고리즘의 분류를 안다면 알고리즘 공부에 도움이 될 수 있고 조금 더 동기 부여가 될거 같아 알고리즘의 분류에 대해 간단한 글을 작성해 보겠습니다.

P Problem 

P Problem에서 P란 다항이란 뜻을 가진 Polynomial에서 따왔습니다. 즉 P Problem이란 Polynomial Time안에 해결할 수 있는 문제를 뜻한다. 여기서 P Algorithm이 아니라 P Problem이라 한 것에 주의 할 필요가 있는데 우리는 주로 문제를 P-NP로 분류하지 알고리즘을 분류하지 않는다.

Polynomial Time에 해결할 수 있다는 문제를 해결하는 알고리즘의 시간복잡도가 O(n^k) | k ∈ R 이하라는 것과 동치이며, 우리는 주로 문제에 대해 동일한 해답을 주는 알고리즘이 있을 때 해당 문제가 해결가능하다고 한다. 

Polynomial Running Time을 갖는 알고리즘을 Efficient (효율적) 한 알고리즘이라 하며 알고리즘 문제는 이러한 Efficient Algorithm을 찾는 것을 목표로 한다.

간단한 예로, 정렬 문제에 대해서 Polynomial Time보다 적은 수행 시간을 가지는 버블정렬, 삽입정렬, 병합정렬, 퀵정렬등이 존재하기 때문에 우리는 주어진 수열에 대한 정렬 문제를 P Problem이라고 하고 각각의 알고리즘은 효율적이라고 할 수 있다. 

---

NP Problem

NP Problem은 Non-deterministic Polynomial Time Problem의 약자이다. 아쉽게도 N-NP 문제는 Polynomial/Non-Polynomial처럼 간단한 차이가 아니다. 어떠한 문제를 해결하는 Non-deterministic Polynomial Time을 가진 알고리즘이 존재한다면 우리는 해당 문제를 NP Problem이라고 한다. NP Problem은 다항식 시간내에 "해결"할 수 있는지 없는지 모르는 문제들이다.

조금 더 쉽게 풀어서 말하자면 어떤 결정 문제에 대해서 답이 있을 때, 문제의 답이 있다는 것을 입증하는 힌트가 주어지면, 그것을 다항식 시간 내에 검증할 수 있는 문제를 NP Problem이라고 한다.

예를 들어 어떤 그래프가 주어졌을 때, "그 그래프의 모든 점을 정확하게 한 번씩만 지나는 경로가 존재하는가?" 하는 문제를 '해밀턴 경로 문제'라고 하는데, 만약 그 답이 Yes이고 모범답안으로서 그 그래프상의 모든 점을 정확하게 한 번씩만 지나는 경로가 주어진다면, '그런 경로가 존재한다'는 것을 확인할 수 있을 것이다.

그렇기에 우리는 P ⊆ NP라고 할 수 있지만 NP ⊆ P인지는 알 수 없다.

---

NP-Hard Problem

정의는 다음과 같다. "모든 NP 문제를 다항식 시간 내에 'A'  문제로 reduce/transform 할 수 있는 경우 'A' 문제를 NP-hard라고 한다."

위 그림에서 T(X)가 transformaiton 함수를 뜻하는데 P 문제의 인풋 x를 Q 문제의 인풋으로 매핑하는 일을 하고 있다. 이러한 x와 y는 다대일 일 수 있기에 다대일 환산이라 하며, 만약 이 변형이 다항시간내에 이루어 진다면 polynomial-time many-one reducible이라 한다.

그렇기에 NP_Hard 문제는 polynomial-time many-one reducible하다고 할 수 있다.

---

NP-Complete Problem

NP-Complete한 문제는 NP-Hard이면서 NP에 속하는 문제를 뜻한다.

NP-Complete한 문제를 풀면 모든 NP 문제를 풀 수 있기에 가장 핵심이 되며, 그렇기에 Complete라는 이름이 붙었다. 그렇기에 NP-Complete 문제가 P 문제라고 증명이 되면 P=NP라는 것이 증명되는 것이기에 역사적으로도 중대한 문제이지만 아직 해결되지 않았다. 

그렇기에 P-NP 문제에 대해 다음과 같은 두가지 그림이 남아있다.