결정 문제(Decision Problem)

결정 문제란, Yes-No로 답할 수 있는 문제를 일컫는다.
가령 'a는 b의 배수인가?'는 결정 문제이다.
앞으로 살펴볼 P 문제와 NP 문제는 모두 결정 문제에 해당한다.

---

P (Polynomial-time)

P는 쉽게 해결(tractable)할 수 있는 결정 문제들의 집합'이다.
다시 말해, 다항 시간 내에 Yes-No로 대답할 수 있는 문제는 P 문제이다.

다루기 쉽고 어려움의 기준은 다항 시간 내에 작업을 완료할 수 있는지 여부이다.
가령 위에서 살펴본 결정 문제 'a는 b의 배수인가?'는 유클리드 호제법을 사용하여 다항 시간 내에 해결할 수 있으므로 P 문제이다.

---

NP(Non-deterministic Polynomial-time)

NP는 '쉽게 해결할 수 있는 비결정적 결정 문제들의 집합'이다.
여기서 '비결정적'이라고 함은 여러 가지 풀이 가능성을 고려할 수 있음을 의미한다.
사실 해를 유일하게 결정하지 않은 것을 해결했다고 말할 수 있는지의 측면에서 보면 위 NP의 정의는 다소 형식적이다.

실질적으로 NP는 쉽게 정답 여부를 확인, 또는 쉽게 검산할 수 있는 결정 문제들의 집합의 의미로 많이 쓰인다.
다시 말해, 어떤 문제의 답이 Yes 또는 No라는 것을 입증하는 힌트가 주어질 때 그 힌트를 사용해 그 문제의 답이 Yes 또는 No라는 것을 다항 시간 내에 확인할 수 있는 문제는 NP 문제이다.

가령 부분집합 합 문제(Subset Sum Problem), 즉 '크기가 n인 어떤 정수 집합이 주어질 때, 이 집합의 부분집합 중 원소의 합이 0이 되는 것이 존재하는가?'는 NP 문제이다.
원소 합이 0이 되는 부분집합을 다항 시간 안에 찾아내는 알고리즘은 알려지지 않았다.
하지만 정수 집합 {-5, 6, 1, 2, -10, -7, 13}에 대해, {6, 1, -7}이라는 힌트가 제공되기만 하면 이 집합이 주어진 집합의 부분집합이고 이 집합의 원소 합이 0이라는 사실을 확인함으로써 이 문제의 답이 Yes라는 검증은 쉽게 할 수 있다.

---

P vs NP

정리하자면, P 문제는 '다항 시간 내에 해결할 수 있는 결정 문제', NP 문제는 '다항 시간 내에 검산할 수 있는 문제'라고 할 수 있다.
따라서 P 문제와 NP 문제는 상호 배타적인 관계가 아니다.

P는 NP의 부분집합이다.

P 문제는 그 문제의 힌트에 관계없이 이미 쉽게 해결되기 때문이다.
'해결'이라 함은 모든 경우에 대해 옳고 그름을 따지는 것이며, '검산'이라 함은 어떤 경우에 대해 옳고 그름을 따지는 것이다.
다항 시간 내에 문제 자체를 해결할 수 있다면, 다항 시간 내에 주어진 답이 맞는지 검산할 수 있는 것은 당연하다.

참고로 P는 '결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류', NP는 '비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제류'라고도 정의할 수 있다.
여기서도 역시, 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있다는 점에서도 P는 NP의 부분집합이 된다.

---

여-NP(co-NP)

여-NP는 '다항 시간 내에 해결 가능한지는 모르겠지만, 틀린 답이 틀렸다는 것을 쉽게 증명 가능한 판정 문제들의 집합'이다.
다시 말해, No에 해당하는 힌트가 제공되었을 때, 그 힌트가 문제의 답이 No임을 다항 시간 내에 증명하는 문제는 여-NP 문제이다.

해밀턴 경로 문제, 즉 '어떤 그래프의 모든 점을 한 번씩만 지나는 경로가 존재하는가?'의 문제는 NP 문제이다.
그 정답이 Yes라면, 모범답안이 주어질 경우 해밀턴 경로가 존재한다고 확인할 수 있을 것이다.

그러나 그 정답이 No라면, 해밀턴 경로를 만족하지 않는 경로가 주어진다고 하더라도 그 경로가 해밀턴 경로가 존재하지 않음을 보여주지는 않는다.
No라는 정답을 다항시간 내에 확인할 수 있게 해주는 힌트는 알려져 있지 않아 아직까지 해밀턴 경로 문제는 여-NP에 해당하지 않는다.

'해밀턴 경로가 존재하지 않는가?'의 문제는 여-NP 문제일 것이다.

---

✏️ P-NP 문제

P-NP 문제는 'P = NP'의 여부를 증명해야 하는 문제이다.
P 집합은 NP 집합의 부분집합이므로, 모든 NP 문제가 P 문제인지 아닌지를 증명하면 된다.
이는 컴퓨터과학 분야의 대표적인 미해결 문제이면서 밀레니엄 문제 중 하나이다.

만약 P = NP라면,

1.
'모든 NP 문제가 사실 P 문제임에도 불구하고 여태 적절한 환원법을 찾지 못해 다항 시간 내에 해결될 수 없었다.'라는 학자들이 쌓아온 노력을 부정하는 듯한 주장이 가능하다.
(환원에 관한 이야기는 아래에서 다룬다.)
NP에서 살펴본 부분집합 합 문제 역시, 지수 시간이 아닌 다항 시간 내에 풀 수 있는 알고리즘이 사실 존재할 것이다.
이런 측면에서 보면 NP는 '다항 시간 내에 해결할 수 없을 것 같지만 아직 확실하지 않은 결정 문제들의 집합'이라고도 정의할 수 있을 것 같다.

2.
또한 '어떤 문제를 쉽게 검산할 수 있다면 그 문제 자체도 쉽게 해결할 수 있다.'는 대단히 강력한 주장 역시 가능해지는데, 이는 직관과 배치되는 일이다.
어떤 방정식 문제에서 해를 직접 구하는 것은 어려울지라도, 이미 알고 있거나 알게 된 해를 방정식에 대입해 그것이 옳은 해인지 검산하는 일은 훨씬 쉽다.

따라서 사실 많은 학자들은 P $\neq$ NP일 것이라 믿는다.

수많은 학자들이 여러 NP 문제들을 마주하며 다항 시간 내에 풀 수 있는 알고리즘을 찾아내려고 노력해 왔지만 그 성과가 없었기 때문이다.
본질적으로 증명은 검증보다 어려운 문제이므로 P와 NP가 같을 수 없다고 생각하기도 한다.

---

NP-난해(NP-Hard)

모든 NP 문제를 다항 시간 내에 문제 'A'로 환원(reduction 또는 transformation)할 수 있는 경우, 이 'A'를 NP-난해 문제라고 부른다.
NP-난해 문제는 다항 시간 내에 풀이될 수도 있고, 아닐 수도 있다.

주어진 n개의 수 중 중간값 계산하는 문제를, 주어진 n개의 수를 오름차순으로 정렬하는 문제로 바꾸어 푸는 것이 환원의 예이다.

또한 NP-난해의 정의에 따르면, NP-난해 문제를 풀 수 있는 알고리즘으로 모든 NP 문제를 풀 수 있게 된다.
이러한 점에서 NP-난해 문제는 NP 문제보다 적어도 어렵거나 같다고 말한다.
NP-난해 문제들은 보통 근사나 휴리스틱한 방법 등 간접적으로 해결된다.

부분집합 합 문제, 외판원 순회 문제(TSP - Travelling Salesman Problem), 정지 문제(Halting Problem) 등이 NP-난해에 해당한다.

---

NP-완전(NP-complete)

NP이면서 NP-난해인 문제, 즉 모든 NP 문제들을 환원시킨 문제가 또 다시 NP 문제가 될 때, 그 문제를 NP-완전 문제라고 부른다.

P-NP 문제를 해결할 수 있다는 점에서 NP-완전의 개념은 중요하다.

• NP-완전 문제가 하나라도 P 문제라면, 결국 모든 NP 문제는 P 문제로 환원될 수 있다는 것이므로 P = NP가 증명된다.
• 반대로 NP-완전 문제가 하나라도 P 문제가 아니라면, P = NP를 부정하는 반례가 된다.

해밀턴 경로 문제, SAT(boolean SATisfiability problem), 배낭 문제(Knapsack Problem), 그래프 색칠 문제(Graph Coloring Problem) 등이 NP-완전에 해당한다.