복잡도 클래스: P, NP, PSPACE의 지도
P와 NP를 넘어 복잡도 클래스들의 전체 지도를 그립니다. 시간과 공간이라는 두 자원, 결정적·비결정적 계산의 차이, P ⊆ NP ⊆ PSPACE ⊆ EXPTIME의 포함 관계, co-NP와 사비치 정리, 그리고 어떤 분리가 증명되었고 무엇이 미해결인지 직관 중심으로 정리합니다.
지난 글에서 NP-완전성을 통해 “어려운 문제”의 경계를 살펴봤습니다. 그런데 P와 NP는 거대한 복잡도 지형의 일부일 뿐입니다. NP보다 더 어려운 문제들, 시간이 아니라 메모리로 정의되는 클래스들, “아니오”를 검증하는 클래스까지 — 이번 글에서는 복잡도 클래스들의 전체 지도를 그려봅니다. 각 클래스가 어떤 자원으로 정의되고 서로 어떻게 포함되는지 이해하면, 알고리즘의 한계를 보는 시야가 한층 넓어집니다.
두 가지 자원: 시간과 공간
복잡도 클래스는 결국 두 가지 질문으로 정의됩니다. 얼마나 많은 시간(연산 횟수)과 얼마나 많은 공간(메모리)을 쓰느냐입니다. 여기에 계산 모델이 결정적(deterministic)인지 비결정적(nondeterministic)인지가 더해집니다.
이 세 축을 조합하면 주요 클래스가 자연스럽게 나옵니다.
| 클래스 | 정의 |
|---|---|
| P | 결정적, 다항 시간 |
| NP | 비결정적, 다항 시간 (= 다항 시간 검증) |
| PSPACE | 결정적, 다항 공간 |
| EXPTIME | 결정적, 지수 시간 |
| co-NP | ”아니오” 답을 다항 시간에 검증 |
포함 관계의 지도
이 클래스들은 깔끔하게 중첩됩니다. 알려진 핵심 포함 관계는 다음과 같습니다.
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
각 포함이 왜 성립하는지 직관적으로 짚어봅시다.
- P ⊆ NP: 다항 시간에 풀 수 있으면, 답을 직접 계산해 검증할 수 있습니다.
- NP ⊆ PSPACE: NP 문제는 가능한 모든 증명서를 하나씩 시도하며 풀 수 있고, 한 번에 하나씩만 메모리에 두면 다항 공간이면 충분합니다(시간은 지수일 수 있지만 공간은 다항).
- PSPACE ⊆ EXPTIME: 다항 공간 기계가 가질 수 있는 서로 다른 상태(구성)의 수는 지수 개뿐입니다. 같은 상태가 두 번 나오면 무한 루프이므로, 지수 시간 안에 반드시 멈춥니다.
공간은 시간보다 너그럽다
흥미로운 사실 하나. 공간은 재사용할 수 있는 자원입니다. 같은 메모리 칸을 계산 내내 몇 번이고 덮어쓸 수 있지만, 시간은 한 번 쓰면 돌아오지 않습니다. 이 비대칭이 강력한 결과로 이어집니다.
사비치 정리(Savitch’s theorem)는 비결정적 다항 공간이 결정적 다항 공간과 같다고 말합니다.
PSPACE = NPSPACE시간 영역에서 P = NP가 미해결인 것과 대조적으로, 공간 영역에서는 결정성과 비결정성의 차이가 이미 사라졌다는 점이 인상적입니다. 비결정적 선택을 결정적 기계가 제곱 공간으로 흉내 낼 수 있기 때문입니다.
co-NP: “아니오”의 세계
NP는 “예” 답에 짧은 증명서가 있는 문제였습니다. 그렇다면 “아니오” 답에 짧은 증명서가 있는 문제는? 그것이 co-NP입니다.
예를 들어 “이 논리식은 충족 불가능한가?”(UNSAT)는 co-NP 문제입니다. 충족 가능함을 보이는 증명서(만족하는 배정)는 짧지만, 충족 불가능함을 보이는 짧은 증명서는 알려져 있지 않습니다. NP = co-NP인가 역시 미해결 문제이며, 만약 다르다면 P ≠ NP도 따라옵니다. 소수 판정처럼 NP와 co-NP 양쪽에 걸친 문제들도 흥미로운 사례입니다.
무엇이 증명되었고 무엇이 미해결인가
이 지도에서 가장 헷갈리는 부분은 무엇을 우리가 실제로 안다고 증명했는가입니다.
- 증명된 분리: P ⊊ EXPTIME. 시간 계층 정리(time hierarchy theorem)에 의해, 충분히 더 많은 시간을 주면 진짜로 더 많은 문제를 풀 수 있음이 증명되었습니다. 따라서 위 사슬 어딘가에는 반드시 진짜 부등호가 있습니다.
- 미해결: 그런데 그 부등호가 정확히 어디인지는 모릅니다. P = NP인지, NP = PSPACE인지, PSPACE = EXPTIME인지 — 중간 단계의 등호 여부는 모두 열린 문제입니다.
즉, “P부터 EXPTIME까지 사이에 적어도 한 번은 진짜로 커진다”는 것만 알 뿐, 어느 지점에서 커지는지는 아무도 증명하지 못한 상태입니다. P = NP는 그중 가장 유명한 미해결 질문일 뿐입니다.
더 넓은 지형
이 글에서 다룬 것은 핵심 골격이고, 실제 복잡도 동물원(complexity zoo)에는 수백 개의 클래스가 있습니다. 몇 가지만 맛보면 다음과 같습니다.
- L / NL: 로그 공간으로 정의되는, P보다 작은 클래스들.
- #P: “해가 몇 개 있는가”를 세는 계수 문제들. NP보다 어렵습니다.
- BPP: 확률적 다항 시간으로 높은 확률로 맞히는 문제들.
- 다항 계층(PH): NP와 co-NP를 번갈아 쌓아 올린 무한 계층.
이 모든 지형의 바닥에 P가, 그 위로 NP가 있고, 우리가 매일 만드는 알고리즘은 대부분 P 안에서 더 작은 지수를 다투는 싸움입니다.
다음 글에서는 이 모든 클래스 분류의 접착제, 한 문제의 어려움을 다른 문제로 옮기는 핵심 도구인 환원(reduction)을 자세히 다룹니다.
지난 글: NP-완전성: 어려운 문제의 경계
다음 글: 환원: 문제의 어려움을 옮기는 기술
읽어주셔서 감사합니다. 😊