NP-완전 (P-NP, 계산 복잡도, 환원)
어떤 문제는 컴퓨터가 아무리 빨라져도 큰 입력에서는 사실상 풀 수 없다. 외판원이 모든 도시를 한 번씩 들러 돌아오는 최단 경로, 강의 시간표를 충돌 없이 짜는 문제, 배낭에 가치를 최대로 담는 문제 — 이들은 입력이 조금만 커져도 가능한 경우의 수가 폭발한다. 이런 "어려움"을 수학적으로 분류하는 이론이 계산 복잡도(Computational Complexity)이며, 그 한가운데에 컴퓨터 과학 최대 난제인 P-NP 문제가 있다. 본 글은 P와 NP의 정의, NP-완전과 NP-난해의 차이, 그리고 문제 사이의 환원이라는 핵심 도구를 세심하게 정리한다(출처: 위키백과 — NP-completeness). 제가 알고리즘 수업에서 외판원 문제에 며칠을 쏟다가 "이건 다항 시간 알고리즘이 알려져 있지 않은 NP-난해 문제"라는 한 줄을 보고 허탈했던 기억이 있는데, 그 경험 이후로는 "문제를 풀기 전에 이 문제가 풀 수 있는 종류인지부터 묻는다"는 태도를 갖게 되었다.
P와 NP — 풀기와 검증하기
복잡도 분류의 출발점은 두 개의 집합이다. P(Polynomial time)는 다항 시간 안에 답을 구할 수 있는 결정 문제들의 집합이다. 여기서 다항 시간이란 입력 크기 n에 대해 O(n), O(n²), O(n³)처럼 n의 거듭제곱으로 표현되는 시간을 가리키며, 정렬·최단 경로·최대 유량 같은 "효율적으로 풀린다"고 여겨지는 문제들이 모두 P에 속한다.
NP(Nondeterministic Polynomial time)는 답이 주어졌을 때 그 답이 옳은지를 다항 시간에 검증할 수 있는 문제들의 집합이다. 핵심은 "푸는 것"과 "검증하는 것"의 구분이다. 예컨대 거대한 수의 소인수분해는 답을 찾기는 어렵지만, 누가 인수들을 제시하면 곱해서 맞는지 확인하는 것은 빠르다. 스도쿠도 푸는 것은 어려워도 채워진 답이 규칙에 맞는지 확인하는 것은 순식간이다. 이렇게 검증이 쉬운 문제가 NP다.
여기서 가장 흔한 오해를 바로잡아야 한다. NP의 N은 "Non-polynomial(비다항)"이 아니라 "Nondeterministic(비결정론적)"이다. NP는 결코 "풀기 어려운 문제"라는 뜻이 아니며, 오히려 P는 NP의 부분집합이다. 다항 시간에 풀 수 있는 문제는 당연히 다항 시간에 검증도 할 수 있기 때문이다. 이 P ⊆ NP는 확실하지만, 그 반대인 P = NP인지 P ≠ NP인지는 아무도 증명하지 못했다.
P-NP 문제 — 컴퓨터 과학의 최대 난제
"검증이 쉬운 모든 문제는 푸는 것도 쉬운가?" 이 한 줄이 P-NP 문제다. 만약 P = NP가 참이라면, 검증할 수 있는 모든 문제는 효율적으로 풀 수도 있다는 뜻이 되어 암호·최적화·신약 설계 등 거의 모든 분야가 뒤집힌다. 반대로 P ≠ NP라면, 본질적으로 검증은 쉽지만 푸는 것은 어려운 문제가 실재한다는 뜻이다.
이 문제는 2000년 클레이 수학연구소가 100만 달러의 상금을 건 일곱 개 밀레니엄 문제 중 하나로, 대다수 전산학자는 P ≠ NP일 것이라 믿지만 증명은 여전히 미해결이다(출처: 위키백과 — P versus NP problem). 현재까지 NP에 속하는 수천 개의 문제 중 어느 하나도 다항 시간 알고리즘이 발견되지 않았다는 사실이 P ≠ NP를 강하게 시사하지만, "발견되지 않았다"는 증명이 아니다.
[복잡도 클래스의 포함 관계 — P ≠ NP라고 가정한 경우]
┌─────────────── NP-난해(NP-hard) ───────────────┐
│ │
┌────┴─────── NP ───────┐ │
│ ┌──── P ────┐ │ ★ NP-완전 = NP ∩ NP-난해 │
│ │ 정렬·최단경로 │ ★검증 가능 │ │
│ └───────────┘ │ (SAT, 외판원 판정, 배낭) │
└───────────────────────┘ │
(정지 문제 등 NP 밖의 난해 문제) │
└─────────────────────────────────────────────────┘NP-완전과 환원 — 어려움의 핵심
NP 안에서도 가장 어려운 문제들의 집합이 NP-완전(NP-complete)이다. 정의는 두 조건의 결합이다. 첫째, 그 문제가 NP에 속한다. 둘째, NP의 모든 문제를 그 문제로 다항 시간에 환원(reduction)할 수 있다. 환원이란 "문제 A를 문제 B로 바꿔 푸는 것"으로, A의 입력을 다항 시간에 B의 입력으로 변환해 B의 답이 곧 A의 답이 되게 만드는 기법이다.
이 환원이 강력한 이유는, NP-완전 문제 중 단 하나라도 다항 시간 알고리즘이 발견되면 환원을 통해 NP의 모든 문제가 다항 시간에 풀려 P = NP가 즉시 증명된다는 점이다. 1971년 스티븐 쿡이 부울 만족 가능성 문제(SAT)가 최초의 NP-완전 문제임을 증명했고(쿡-레빈 정리), 이후 외판원 판정 문제·배낭 문제·그래프 색칠·해밀턴 경로 등 수천 개 문제가 SAT로부터의 환원을 통해 NP-완전임이 밝혀졌다.
| 분류 | 정의 | 대표 예시 |
|---|---|---|
| P | 다항 시간에 풀 수 있음 | 정렬, 최단 경로, 최대 유량 |
| NP | 다항 시간에 검증 가능 | 소인수분해, 스도쿠, P 전체 |
| NP-완전 | NP에 속하며 NP의 모든 문제가 환원됨 | SAT, 외판원(판정), 배낭, 그래프 색칠 |
| NP-난해 | NP의 모든 문제가 환원되나 NP 소속은 불필요 | 외판원(최적화), 정지 문제 |
여기서 NP-난해(NP-hard)와 NP-완전의 차이를 짚어야 한다. NP-난해는 "NP의 모든 문제만큼 어렵다"는 조건만 만족하면 되고, 자신이 NP에 속할 필요는 없다. 따라서 검증조차 불가능한 정지 문제(halting problem) 같은 것도 NP-난해에 포함된다. NP-완전은 그중에서 NP에도 속하는, 즉 "어렵지만 검증은 되는" 문제들의 교집합이다.
어려운 문제를 마주했을 때의 실전 전략
문제가 NP-완전이라고 판명되면 손을 놓아야 할까? 그렇지 않다. 실무에서는 여러 우회 전략을 쓴다. 첫째, 근사 알고리즘으로 최적해 대신 "최적의 1.5배 이내" 같은 보장된 근사해를 다항 시간에 구한다. 둘째, 휴리스틱으로 이론적 보장은 없지만 실전에서 잘 동작하는 해를 빠르게 찾는다(유전 알고리즘, 담금질 기법 등). 셋째, 입력 크기가 작거나 특수한 구조를 가지면 정확한 지수 알고리즘(예: 외판원의 비트마스킹 DP, O(2ⁿ·n²))이 현실적으로 충분하다.
흔한 오해 하나를 더 짚으면, "NP-완전 문제는 절대 풀 수 없다"는 통념이다. 실제로는 입력이 작으면 지수 알고리즘으로 정확히 풀리고, 크면 근사·휴리스틱으로 충분히 좋은 해를 얻는다. 즉 NP-완전은 "포기 신호"가 아니라 "전략을 바꾸라는 신호"다. 시험에서는 P·NP·NP-완전의 정의와 포함 관계, SAT가 최초의 NP-완전 문제라는 사실이 단골 출제되며, 실무에서는 "이 문제가 NP-난해인가"를 빨리 판단해 다항 시간 알고리즘을 헛되이 찾는 시간을 아끼는 것이 가장 값진 능력이다. 솔직히 이 분류 체계를 배우기 전과 후의 가장 큰 차이는, 안 풀리는 문제 앞에서 "내 실력이 부족한가"를 의심하던 태도가 "이 문제가 본질적으로 어려운 종류인가"를 먼저 묻는 태도로 바뀌었다는 점이다.
메타 디스크립션: 컴퓨터 과학 최대 난제 P-NP 문제를 중심으로 P·NP의 정의, NP-완전과 NP-난해의 차이, 문제 사이의 환원, 그리고 NP-완전 문제를 만났을 때의 근사·휴리스틱 전략까지 입문자 관점에서 오해를 바로잡으며 세심하게 정리합니다.