P vs NP (계산 복잡도

P vs NP — 세상에서 제일 유명한 미해결 문제

"정답을 찾는 것"과 "누가 준 답을 맞는지 확인하는 것"은 얼마나 다를까? 스도쿠를 푸는 건 오래 걸려도, 다 채워진 스도쿠가 맞았는지 검사하는 건 몇 초면 된다. 이 "검증은 쉬운데 풀이는 어려워 보이는" 문제들의 모임이 NP다. 그리고 "검증이 쉬우면 풀이도 사실은 쉬운 것 아닐까?", 즉 P = NP인지 아무도 모른다. 이걸 증명하면 클레이 연구소가 상금 100만 달러를 준다 (2000년~).

1. P와 NP, 한 문장 정의

P (Polynomial) — 입력 크기 n에 대해 n², n³ 처럼 다항식 시간에 답을 구할 수 있는 문제. 예: 정렬, 최단 경로, 소수 판정.
NP (Nondeterministic Polynomial) — 누가 "이게 답이야"라고 증거(certificate)를 주면 그게 맞는지 다항식 시간에 검증할 수 있는 문제. 예: 스도쿠, 부분집합 합, 외판원(예산 이하 경로).
정렬처럼 빨리 풀 수 있으면 당연히 빨리 검증도 된다 → P ⊆ NP. 반대(NP ⊆ P)는 미해결.

P ⊆ NP 는 확실 | P = NP ? 는 미해결

2. 직접 느껴보기 — 부분집합 합 (Subset Sum)

아래 숫자 카드 중 일부를 골라 합이 목표값이 되게 만들어라. 카드를 눌러 담거나 뺄 수 있다. 정답을 찾는 것은 감으로 이것저것 시도해야 하지만, 일단 고른 조합이 맞는지 확인하는 건 그냥 더하기 한 번이다 — 이게 NP의 핵심 감각이다.

목표 합 = —

고른 합: 0

3. 컴퓨터에게 "그냥 다 해보게" 시키면?

카드가 n개면 담는다/뺀다 조합은 2ⁿ가지다. 똑똑한 수 없이 전부 확인하는 완전 탐색을 돌려보자. n을 몇 개만 올려도 확인해야 할 조합 수가 폭발한다.

n = 20

확인한 조합: 0 / 1,048,576 경과: 0 ms

같은 속도라면 n = 60 짜리 문제 하나에 우주 나이보다 오래 걸린다. "빠른 컴퓨터"로는 절대 못 이긴다 — 알고리즘이 필요하다.

4. 다항 vs 지수 — 숫자로 보는 격차

1초에 10억(10⁹) 번 연산하는 컴퓨터가 입력 크기 n을 처리하는 데 걸리는 시간:

n	n² (다항)	n³ (다항)	2ⁿ (지수)	n! (계승)
10	0.1 µs	1 µs	1 µs	3.6 ms
30	0.9 µs	27 µs	1 초	10²⁰ 년
50	2.5 µs	125 µs	13 일	우주 나이 ×10⁴⁴
100	10 µs	1 ms	4×10¹³ 년	— (상상 불가)

다항식은 n이 2배 되면 시간이 몇 배로 늘지만, 2ⁿ은 n이 1 늘 때마다 2배가 된다.

5. NP-완전 — "다 같은 문제였다"

1971년 쿡과 레빈은 놀라운 걸 증명했다. NP 안의 어떤 문제(SAT: 논리식을 참으로 만드는 대입이 있나?)는 NP의 모든 문제를 다항 시간에 흉내 낼 수 있다. 이렇게 "NP에서 제일 어려운" 문제들을 NP-완전이라 한다.

문제 A를 문제 B로 다항 시간 변환(환원)할 수 있으면 "B를 풀면 A도 풀린다". NP-완전 문제들은 서로 환원으로 연결돼 있어서, 단 하나라도 다항 시간 알고리즘을 찾으면 전부 무너지고 P = NP가 된다. 반대로 하나라도 "절대 불가능"을 증명하면 P ≠ NP.

SAT → 3-SAT → 클리크 → 정점 커버 → 부분집합 합 → 해밀턴 경로 → …

NP-완전 예시: 스도쿠(n×n), 부분집합 합, 배낭 문제, 외판원 결정형, 그래프 색칠, 지뢰찾기 일관성, 테트리스 최적 배치
NP-하드: "NP-완전만큼 어렵지만 NP에 속하는지는 별개"인 문제 (예: 바둑 일반화, 정지 문제는 아예 결정 불가)

6. 세 동네 지도 (그리고 P = NP 라면?)

P: 빨리 풀림 NP: 빨리 검증됨 NP-완전: NP에서 가장 어려움 NP-hard: NP-완전 이상

대부분의 연구자는 P ≠ NP(그림처럼 P가 NP보다 작다)라고 믿지만, 증명은 없다. 버튼을 눌러보면 P = NP일 때 세상이 어떻게 바뀌는지 볼 수 있다.

7. 검증기는 이렇게 짧다 (부분집합 합)

# 검증: 증거(고른 인덱스들)를 받아 맞는지 확인 — O(n), 아주 빠름
def verify(nums, target, chosen_idx):
    return sum(nums[i] for i in chosen_idx) == target

# 풀이: 증거를 스스로 찾아야 함 — 완전 탐색은 O(2ⁿ)
def solve(nums, target):
    n = len(nums)
    for mask in range(1 << n):              # 2ⁿ 개의 부분집합
        s = sum(nums[i] for i in range(n) if mask >> i & 1)
        if s == target:
            return [i for i in range(n) if mask >> i & 1]
    return None

verify는 몇 줄이고 항상 빠르다. solve는 지금까지 누구도 이 문제류에서 다항 시간 버전을 못 만들었다 — 하지만 "불가능하다"는 증명도 없다. 그 간극이 바로 P vs NP다.

8. 한 줄 요약

P는 빨리 푸는 문제, NP는 빨리 채점되는 문제. 정렬처럼 겹치는 것도 많지만, 스도쿠·부분집합 합 같은 NP-완전 문제는 채점은 순식간인데 푸는 좋은 방법이 안 보인다. 이 둘이 사실 같은 반(P = NP)인지 50년 넘게 아무도 모른다 — 알아내면 암호가 무너지고 최적화가 공짜가 되며, 100만 달러를 받는다.