P, NP

Polynomial time

다항 시간

다항 시간이란 알고리즘의 실행 시간이 입력 크기 n에 대한 다항식으로 표현되는 경우를 말합니다. 이는 O(n^k ) (k는 양의 상수)와 같은 형태로 나타나는 시간 복잡도를 의미한다.

 

O(n), O(n²), O(n³ + n² + 3), O(log n), O(1) 등은 모두 다항 시간으로 분류되는데 O(log n), O(1)의 경우 엄밀히 말하면 다항식은 아니지만 다항 시간보다 훨씬 효율적이므로 넓은 의미에서 다항 시간 범주에 포함된다.

 

반면 O(2ⁿ), O(n!)과 같은 복잡도는 다항 n이 커질수록 기하급수적으로 실행시간이 폭증하여 다항 시간이 아니며, 이런 알고리즘은 대개 비실용적으로 간주한다.

 

어떤 문제에 대해 다항 시간 내에 항상 정답을 찾을 수 있는 알고리즘이 존재한다면, 그 문제는 Class P에 속한다. 

NP

비결정적 다항 시간(Nondeterministic Polynomial time)이란, 어떤 문제에 대해 정답이 주어졌을 때, 그 정답이 올바른지 다항 시간 내에 검증이 가능한 문제들을 말한다.

 

즉, 해를 찾는 과정은 어려울 수 있지만, 해가 주어졌을 때 그 해를 확인하는 것은 쉽고 빠르다.

 

예를 들어 아주 큰 숫자를 소인수분해하는 것은 시간이 오래 걸리는 어려운 문제이다. 하지만 누군가 소인수의 정답을 알려준다면, 그 답들을 곱해서 원래 숫자가 나오는지 확인하기만 하면 되며 이 곱셈 연산은 다항 시간 안에 완료할 수 있으므로 이런 문제를 NP에 속한다고 한다.

 

NP-complete

NP에 속하는 문제들 중에서 가장 어려운 문제들의 집합이다. 

- NP에 속한다 : 정답이 주어졌을 때 다항 시간 내에 검증이 가능하다.

- NP-환원성 : NP에 속하는 모든 다른 문제들을 다항 시간 내에 NP-complete 문제로 변환할 수 있다.

 

NP-환원성은 핵심적인 특징으로 이는 NP-complete 문제 중 하나라도 다항 시간 내에 해결할 수 있는 알고리즘을 찾는다면, 이론적으로 NP에 속하는 모든 문제도 다항 시간 내에 해결할 수 있게 된다는 의미를 가진다.

 

예) SAT 만족 가능성 문제, 3-CNF SAT, TSP(결정형), 그래프 색칠 문제

 

NP-hard

NP-complete보다 더 넓은 개념으로, NP의 모든 문제만큼 어렵거나 그 이상일 수 있는 문제들이다. NP-complete와 유사하게 NP에 속하는 모든 문제를 다항 시간 내에 자기 자신으로 환원할 수 있어야 하지만 반드시 NP에 속할 필요는 없다. 즉, 해가 주어져도 그 검증조차 다항 시간 안에 불가능할 수 있다. 주로 최적값 찾기 문제나 결정 불가능한 문제들이 NP-hard에 속한다.

 

예) TSP(최적 경로 길이 구하기), 체스 문제, 할터 문제(Halting Problem)

 

┌─── P (다항 시간에 풀 수 있는 문제들)
│
├─── NP (정답 검증이 다항 시간인 문제들)
│          │

│          └─ NP-complete (NP 중 가장 어려운 문제들)
│
└─── NP-hard (NP보다 어려울 수도 있는 문제들)
            │

            └─ NP-complete ⊆ NP-hard

 

 

P vs NP

밀레니엄 문제 중 하나로, P와 NP 사이의 관계는 아직도 해결되지 못한 문제이다.

 

- P : 다항 시간 내에 문제를 풀 수 있는 문제들의 집합이다.

- NP : 정답이 주어졌을 때, 그 정답이 다항 시간 내에 검증될 수 있는 문제들의 집합이다.

 

다항 시간 안에 해를 찾을 수 있는 문제라면 당연히 그 해가 맞는지도 다항 시간 안에 검증할 수 있기 때문에 P ⊆ NP는 항상 참이다. 진정한 문제는 P = NP인가 P ≠ NP인가에 대한 질문으로, 정답을 빠르게 검증할 수 있다면 답을 빠르게 구할 수도 있는가?이다.