[알고리즘 Algorithm] P, NP 문제와 NP-hard, NP-complete 개념 정리

결정 문제(decision problem)과 결정론/비결정론에 대해 짚고 나서 P, NP problem에 대해서 공부하겠다.

 

<목차>
- 결정문제(decision problem)
- 결정론/비결정론 알고리즘 (deterministic / non-deterministic algorithm)
- P (Polynomial time) 문제
- NP (Non-deterministic polynomial time) 문제
- P vs NP 문제
- NP-hard 문제
- NP-Complete 문제
- 결론

 

---

결정 문제 (Decision problem)

주어진 입력에 대해 "예" 또는 "아니오"로 답을 할 수 있는 문제이다. 

이와 반대되는 개념으로, 답이 셋 이상의 경우의 수가 있는 문제를 함수형 문제(function problem)이라고 한다.

 

결정 문제의 예:

• 자연수 a,b가 주어졌을 때, a는 b의 배수인가?
• 자연수 n이 주어졌을 때, n이 소수인가?

함수형 문제의 예:

• 자연수 a,b가 주어졌을 때, a는 b의 최대공배수를 구하여라.
• 자연수 n이 주어졌을 때, n의 약수는 몇 개인가?

---

결정론 / 비결정론 알고리즘 (Deterministic / Non-deterministic alogrithm)

결정론 (deterministic) 알고리즘 : 각 단계에서 그 다음 단계가 유일하게 결정되는 알고리즘.

                                                       즉, A -> B로 결정되어 있는 알고리즘

 

비결정론 (non- deterministic) 알고리즘: 각 단계에서 그 다음 단계가 유일하게 결정되지 않는 알고리즘.

                                                                  즉, A -> B,C,D 인지 정해지지 않음

---

P (Polynomial time) 문제

결정론(deterministic) 알고리즘으로 다항 시간(polynomial time) 내에 해결 가능한 결정 (decision) 문제이다.

즉, P는 yes/no로 답할 수 있는 문제이다.

 

- 다항 시간 (polynomial time)이란?

   어떤 문제를 다항식 시간 내에 풀 수 있다.

   = 다항식 시간 알고리즘을 가진다

   = 다항식 시간복잡도를 가진다. ex) O(logn), O(n), O(n^2),...

   = 지수시간(exponential time)이 아닌 다항식 시간복잡도를 가진다

 

- 다항식 시간복잡도를 가진 알고리즘으로 해결되지 않는 문제들은 지수시간 (exponential time) 시간복잡도를 가진 알고리즘으로 해결된다. ex) O(2^n)

 

P 문제의 예시:   - a는 b의 배수인가?   - 크기가 n인 어떤 정수 집합이 주어질 때, 이 집합을 정렬하시오.

 

해당 문제들은 다항 시간 내에 해결할 수 있으므로 P문제이다.

 

P 문제들의 모임을 P-class라 한다. 

---

NP (Non-deterministic polynomial time) 문제

비결정론(non-deterministic) 알고리즘으로 다항 시간(polynomial time) 내에 해결 가능한 결정(decision) 문제이다.

 

실질적으로, 다항 시간내에 해결할 수 있는 방법이 있지는 않지만,

만약 solution을 찾게되면 다항 시간내에 해결이 가능하다라고 이해하면 된다. 

 

즉, 어떤 문제의 답이 yes 또는 no라는 것을 입증하는 힌트가 주어질 때, 

힌트를 사용해 그 문제의 답이 yes 또는 no라는 것을 다항시간 내에 확인할 수 있는 문제는 NP 문제이다.

 

아래의 조건을 모두 만족하면 NP문제이다.

- 주어진 입력에 대해 하나의 해를 추측한다

- 그 해를 다항식 시간 내에 확인한다

- 그 해가 yes/no로 답한다

 

NP 문제의 예시:   - 크기가 n인 어떤 정수 집합이 주어질 때, 이 집합의 부분 집합 중 원소의 합이 0이 되는것이 존재하는 가?   - 소수 찾기    - 수도쿠

 

해당 문제 중 첫번째 문제를 확인해보자.

원소 합이 0이 되는 부분집합을 다항시간 내에 찾는 알고리즘은 알려지지 않았다.

예를 들어, 주어진 정수 집합 { -3, -2, 5, -10, -7, 10}에서 부분집합{-3, -2, 5}라는 힌트가 제공되기만 하면,

이 집합이 주어진 집합의 부분집합이고, 이 부분집합의 원소 합이 0임을 확인하면,

이 문제의 답이 yes라는 검증은 쉽게 할 수 있다.

 

NP 문제들의 모임을 NP-class라고 한다.

---

P vs NP 문제

P문제는 '다항시간내에 해결할 수 있는 결정 문제', NP문제는 '다항시간 내에 검산할 수 있는 문제'

 

P problem	NP problem
다항 시간 알고리즘이 존재 O 다항 시간 내에 검증 가능	다항 시간 알고리즘이 존재 x 다항 시간 내에 검증 가능

 

 

따라서, P는 NP의 부분집합이다!! (P⊆ NP)

여기서, P⊆ N라고 할 수는 있지만 NP ⊆ P 인지는 알 수 없다.

 

P 문제는 어떤 힌트가 주어지든 간에 이미 쉽게 해결될 수 있는 문제이다.

여기서, '해결'이란 모든 경우을 고려하여 옳고 그름을 따지는 것을 의미하며,

             '검산'은 주어진 답이 옳은지 검증하는 것을 의미한다.
만약 문제를 다항 시간 내에 해결할 수 있다면, 주어진 답이 맞는지 검산할 수 있는 것은 당연하다.

 

NP는 NP-Complete와 NP-hard로 나뉜다.

---

NP-hard 문제

"모든" NP 문제를 다항시간 내에 어떤 문제 A로 환원(reduction)할 수 있다면, 그 A 문제를 NP-hard라고 한다.

 

적어도 NP문제보다는 어려우며, 다항 시간내에 풀 수 없는 문제를 말한다.

다항 방정식 대신에 지수 방정식으로 풀 수 있는 문제를 말한다. 즉, 결정적 다항식으로 구성할 수 없다는 것이다.

(그렇다고 NP-hard라고 해서 다항식이 아니라는 것은 아니지만, 다항식으로 표현될 수 있을 지 여부가 아직 안알려짐)

 

모든 NP 문제 L에 대하여,  L ≤p A이면, A는 NP-hard 문제이다.

 

위 정의에서 ≤p 는 다항식 시간 변환을 말한다. 즉, NP의 모든 문제가 A로 변환이 가능하면 A는 NP-hard 문제인 것이다.

 

NP-hard란 TSP와 같이 모든 경우의 수를 일일히 확인하는 방법외에는 다항식처럼 답을 풀이할 수 없는 문제들을 말한다.

 

그리고, 모든 NP문제가 NP-hard 문제로 다항 시간 내에 변환 가능해도, NP-hard 문제는 반드시 NP 문제일 필요는 없다. ex) NP-Hard 문제이지만 NP 문제는 아닌 것: 정지 문제

 

환원(reduction)

환원(reduction)은 알고리즘에서 문제의 난이도를 다룰 때 사용되는 개념이다.

 

간단한 예시를 보자.

곱셈에 대한 문제와 덧셈에 대한 문제가 있을 때, 곱셉은 곱하는 수만큼 덧셈을 반복하는 과정일 뿐이므로 덧셈을 할 수 있다면 곱셉 문제를 해결할 수 있다. 이 경우 덧셈 문제를 곱셈 문제보다 어렵다고 정의한다. 따라서, 정의에 따라 NP-hard 문제는 모든 NP문제보다 난이도가 어렵다고 말할 수 있다.

 

또 다른 예시를 보자.

문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제, 문제 B: 주어진 n개의 숫자의 큰 값을 계산하는 문제

 

어떤 사람이 문제 A를 쉽게 풀 수 있다면, 그 사람은 문제 B도 쉽게 풀 수 있다. 그 이유는 주어진 숫자들을 정렬한 후, 정렬된 숫자들 중 끝에 있는 값을 선택하기만 하면 그 숫자가 최값이 되기 때문이다. 이처럼 문제 B를 해결하는 과정에서 문제 A를 활용할 수 있으면, 우리는 문제 B를 문제 A로 환원(reducible)할 수 있다고 한다. 즉, 문제 B를 해결하려면 문제 A를 해결하면 되므로, 문제 A는 문제 B보다 더 어렵거나 최소한 난이도가 같다고 볼 수 있다. 여기서 "환원한다"는 것은, 더 쉬운 문제(최대 값 계산 문제)를 해결하기 위해 더 어려운 문제(정렬 문제)를 사용한다는 의미다.

 

환원 과정을 찾는다는 것은 중요한 의미를 갖는다. 어떠한 복잡한 문제가 주어졌을 때, 이미 알고있는 문제를 반복적으로 해결하여 그 문제를 풀 수 있다는 점을 알게 된다면, 완전히 새로운 코드를 작성하는 것보다 응용하는 것이 더 효율적이다. 이는 시간과 노력을 절약하는 데 큰 도움이 된다.

---

NP-Complete 문제

위의 NP-hard의 정의에서 한가지가 더 추가되면 NP-complete이다.

A는 NP이다.

 

즉, NP-complete는 NP 문제이면서 NP-hard 문제이다. 

 

NP-hard 문제는 모든 NP 문제 중에서 가장 어려운 문제이다. 

어떤 해가 정당한지 다항 시간 내에 확인이 가능하다 (NP 문제)

어떤 NP-complete 문제 중 하나라도 다항 시간 내에 풀 수 있다면, 환원(reduction) 과정을 통해 모든 NP 문제를 다항 시간 내에 풀 수 있다. 따라서 NP-complete 문제 하나를 다항 시간 내에 해결할 수 있다면, P=NP임을 증명할 수 있다.

 

현재 NP-complete 문제를 위한 모든 알려진 알고리즘들은 지수적인(exponential) 시간을 요구한다. NP-complete 문제를에 대해서는 완전한 정답을 찾기보다는 훨씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족한다. 어떤 더 빠른 알고리즘이 있는지는 모른다. 어떤 명백하지 않은 문제 (non-trivial) 크기의 NP-Complete를 해결하기 위해서, 다음과 같은 접근 방법 중 하나를 사용한다.

• 근사(Approximation): 어떤 알려져 있는 적절한 범위내에 있는 차선의 (suboptimal) 해결책을 빠르게 찾는 알고리즘. 모든 NP-Complete 문제가 good approximation algorithms을 가진 것은 아니며, good approximation algorithms을 발견한 문제도 문제 그자체를 해결하기에 충분하지는 않다.
• 확률(Probabilistic): 문제의 instance 에 대한 확률 분포 (이상적으로는 "hard" 입력에 대해 낮은 확률을 할당하는) 에 대해 훌륭한 평균 runtime behavior 를 낳는다고 입증된 알고리즘
• 휴리스틱(Heuristic): 많은 경우에 "reasonably well" 작동하지만, 항상 빠르다는 증명은 없는 알고리즘
• Special cases: 문제의 instance 가 어떤 특별한 경우에 속한다면 빠르다는 것이 입증된 알고리즘

NP-complete의 예로 해킹이 있다. 해킹은 모든 비밀번호를 대입해보는 방법이므로 brutal force말고는 적절한 알고리즘이 없다. (다른 예시에는 해밀턴 경로, 팩토리얼 등이 있음)

 

어떤 새로운 문제가 NP-Complete하다는 것을 증명하는 가장 쉬운 방법은, 이미 알려진 NP-Complete 문제를 그것으로 환원(reduction)하는 것이다. 

---

결론

 

P=NP인지 P≠NP인지 아직 증명되지 않았기 때문에 두 개의 다이어그램이 존재한다. 

 

P = NP라고 증명이 된다면, 현재 NP인 모든 문제들이 전부 P 문제로서 풀릴 수 있다는 의미이다.

반대로 생각해서 P != NP가 증명이 된다면, 수많은 NP 문제들이 P 문제로 환원될 수 없다고 증명됐으니 더 쉬운 방법(P 문제로 환원할 방법)을 찾으려고 애쓸 필요가 없다. 즉 이건 어려운 문제니까 쉬운 문제로 만드려고 해봤자 소용 없다는 걸 알게 되는 것이다.

 

---

참조

https://wkdtjsgur100.github.io/P-NP/

https://jusths.tistory.com/122

https://ottl-seo.tistory.com/94