계산 복잡도: P, NP, NP 완전

계산할 수 있는 문제 가운데 현실적인 시간 안에 풀 수 있는 것은 무엇인지 따져요. 빠르게 풀 수 있는 문제 P와 답을 빠르게 확인할 수 있는 문제 NP를 부분집합의 합으로 비교하고, 시험 시간표 짜기를 SAT 문제로 바꿔 푸는 환원을 직접 해 보며 NP 완전의 뜻을 이해해요. 컴퓨터 과학 최대의 미해결 문제인 P와 NP의 관계가 암호에 주는 의미, 어려운 문제를 만났을 때 쓰는 다 따지기, 근사, 휴리스틱 전략을 외판원 문제로 확인하고, 양자 컴퓨터가 할 수 있는 일과 없는 일까지 짚어요.

전문가강의 5 / 5약 14분

지난 강의는 "계산할 수 있는가"를 따졌어요. 이번에는 계산할 수 있는 문제들 사이의 차이를 봐요. 알고리즘 트랙의 복잡도 강의에서 O(n²)과 O(2ⁿ)의 차이를 봤죠. n = 80에서 O(2ⁿ)은 1초에 10억 번 계산해도 3,831만 년이었어요. 계산 복잡도 이론은 이 차이를 알고리즘이 아니라 문제 자체의 성질로 끌어올려서, "이 문제는 어떤 알고리즘을 써도 본질적으로 어려운가"를 묻는 분야예요.

빠르다는 기준: 다항 시간

이론에서는 입력 크기 n에 대해 n², n³처럼 다항식으로 나타나는 시간을 "빠르다", 2ⁿ이나 n!처럼 그보다 빨리 자라는 시간을 "느리다"로 나눠요. n¹⁰⁰도 다항식인데 빠르다고 할 수 있느냐고 물을 수 있어요. 옳은 지적이지만, 실제로 발견되는 다항 시간 알고리즘은 대개 지수가 작고, 컴퓨터나 계산 모델을 바꿔도 다항식은 다항식으로 남는다는 장점이 있어서 이 기준을 써요.

다항 시간에 풀 수 있는 문제의 모임이 P예요. 알고리즘 트랙에서 다룬 정렬, 다익스트라의 최단 경로, 편집 거리, 이진 탐색이 모두 P에 들어요.

NP: 답을 빠르게 확인할 수 있는 문제

어떤 문제는 답을 찾기는 어려워 보이는데, 누가 답을 알려 주면 맞는지 확인하기는 쉬워요. 수 목록에서 합이 정해진 값이 되는 부분집합을 찾는 부분집합의 합 문제가 그래요.

import random
from itertools import combinations

def find_subset(nums, target):                       # 모든 부분집합을 하나씩 시험해요
    checked = 0
    for size in range(len(nums) + 1):
        for combo in combinations(nums, size):
            checked += 1
            if sum(combo) == target:
                return combo, checked
    return None, checked

def verify(nums, target, answer):                    # 답이 주어지면 확인은 금방이에요
    return sum(answer) == target and all(answer.count(x) <= nums.count(x) for x in answer)

random.seed(11)
for n in (10, 15, 20):
    nums = random.sample(range(1, 10**6), n)
    target = sum(nums) // 2 + 1
    answer, checked = find_subset(nums, target)
    print(f"n={n}: 답 {'있음' if answer else '없음'}, 시험한 부분집합 {checked:,}개 (모두 {2**n:,}개)")

nums = [3, 34, 4, 12, 5, 2]
answer, checked = find_subset(nums, 9)
print("합이 9인 부분집합:", answer, "| 확인:", verify(nums, 9, list(answer)))
n=10: 답 없음, 시험한 부분집합 1,024개 (모두 1,024개)
n=15: 답 없음, 시험한 부분집합 32,768개 (모두 32,768개)
n=20: 답 없음, 시험한 부분집합 1,048,576개 (모두 1,048,576개)
합이 9인 부분집합: (4, 5) | 확인: True

답이 없으면 부분집합을 모두 시험해야 하고, 그 수는 n이 하나 늘 때마다 두 배가 돼요. 20개면 100만 개가 넘고, 100개면 세계에서 가장 빠른 슈퍼컴퓨터로도 수만 년이 넘게 걸려요. 그런데 (4, 5)라는 답을 받으면 더해 보기만 하면 돼요. 이렇게 답이 맞는지를 다항 시간에 확인할 수 있는 문제의 모임이 NP예요. 확인에 쓰는 답을 증거라고 해요. 스도쿠도 그래요. 다 채운 판이 맞는지는 줄과 칸을 훑어보면 금방 알지만, 빈 판을 채우기는 어려워요.

NP는 "다항 시간이 아니다"의 줄임말이 아니라 비결정적 다항 시간(Nondeterministic Polynomial)의 줄임말이에요. 오토마타 강의의 NFA처럼 갈림길에서 늘 정답 갈래를 골라 가는 기계가 다항 시간에 풀 수 있다는 뜻인데, 이게 "증거를 받으면 다항 시간에 확인할 수 있다"와 같은 말이에요. 정답 갈래를 고르는 일이 곧 증거를 받는 일이니까요.

P에 든 문제는 확인도 당연히 빠르니 P는 NP에 들어가요. 문제는 그 반대예요. NP의 모든 문제가 P에도 들까요? 즉 답을 빠르게 확인할 수 있으면 언제나 빠르게 찾을 수도 있을까요? 이게 P 대 NP 문제예요.

환원: 문제를 다른 문제로 바꾸기

복잡도 이론의 핵심 도구는 환원이에요. 문제 A를 문제 B로 바꿔 풀 수 있다면, B가 빠르게 풀릴 때 A도 빠르게 풀려요. 예를 들어 볼게요. 같은 학생이 함께 듣는 과목끼리 시험 시간이 겹치지 않게 시간표를 짜는 문제예요. 과목을 정점, 겹치면 안 되는 관계를 간선, 시간대를 색으로 보면 그래프 색칠 문제가 돼요. 이걸 다시 SAT(논리식을 참으로 만드는 참과 거짓의 조합 찾기) 문제로 바꿔서, 시간표를 짜는 코드는 한 줄도 없이 SAT 풀이로만 풀어 볼게요.

from itertools import product

def solve_sat(clauses, n_vars):                      # 변수들의 참/거짓 조합을 모두 시험하는 가장 단순한 SAT 풀이
    tried = 0
    for values in product([False, True], repeat=n_vars):
        tried += 1
        if all(any(values[abs(lit) - 1] == (lit > 0) for lit in clause) for clause in clauses):
            return values, tried
    return None, tried

def coloring_to_sat(n_nodes, edges, colors=3):       # "정점 v가 색 c다"를 변수 하나로 두고, 규칙을 절로 바꿔요
    var = lambda v, c: v * colors + c + 1
    clauses = []
    for v in range(n_nodes):
        clauses.append([var(v, c) for c in range(colors)])           # 적어도 한 색은 칠하고
        for c1, c2 in combinations(range(colors), 2):
            clauses.append([-var(v, c1), -var(v, c2)])               # 두 색을 한꺼번에 칠하지는 않고
    for a, b in edges:
        for c in range(colors):
            clauses.append([-var(a, c), -var(b, c)])                 # 이웃끼리는 같은 색이면 안 돼요
    return clauses, n_nodes * colors

subjects = ["수학", "영어", "물리", "화학", "역사"]
conflicts = [(0, 1), (0, 2), (0, 4), (1, 2), (2, 3), (2, 4), (3, 4)]   # 같은 학생이 함께 듣는 과목
clauses, n_vars = coloring_to_sat(len(subjects), conflicts)
values, tried = solve_sat(clauses, n_vars)
slots = ["1교시", "2교시", "3교시"]
table = {subjects[v]: slots[c] for v in range(len(subjects)) for c in range(3) if values[v * 3 + c]}
print(f"변수 {n_vars}개, 절 {len(clauses)}개 | 시험한 조합 {tried:,}개 (모두 {2**n_vars:,}개)")
print("시간표:", table)
print("겹치는 과목끼리 시간이 모두 다른가요?", all(table[subjects[a]] != table[subjects[b]] for a, b in conflicts))
변수 15개, 절 41개 | 시험한 조합 5,387개 (모두 32,768개)
시간표: {'수학': '3교시', '영어': '2교시', '물리': '1교시', '화학': '3교시', '역사': '2교시'}
겹치는 과목끼리 시간이 모두 다른가요? True

"수학이 1교시다" 같은 문장을 참이나 거짓이 되는 변수 하나로 두고, 시간표의 규칙을 "이 중 적어도 하나는 참" 꼴의 절 41개로 바꿨어요. 그다음은 SAT 풀이에 맡겼을 뿐이에요. 절의 수는 과목과 겹침의 수에 비례해서 늘어나니, 바꾸는 일 자체는 다항 시간이에요. 여기서 짠 SAT 풀이는 조합을 하나씩 시험하는 가장 단순한 방식이지만, 실제 SAT 풀이 프로그램은 똑똑하게 가지를 쳐서 변수가 수백만 개인 산업 문제도 풀어요. 반도체 회로 검증, 소프트웨어 패키지의 버전 맞추기, 근무표 짜기가 이렇게 SAT로 바뀌어 풀려요.

NP 완전: NP에서 가장 어려운 문제들

1971년 스티븐 쿡은(따로 레오니드 레빈도) NP의 모든 문제를 SAT로 환원할 수 있다는 것을 증명했어요. 어떤 NP 문제든 "답을 확인하는 프로그램"이 있으니, 그 프로그램이 돌아가는 과정을 커다란 논리식으로 옮길 수 있다는 아이디어예요. 그래서 SAT가 빠르게 풀리면 NP의 모든 문제가 빠르게 풀려요. 이렇게 NP에 속하면서 NP의 모든 문제가 환원되는 문제를 NP 완전이라고 해요.

이듬해 리처드 카프가 그래프 색칠, 배낭 문제, 해밀턴 순환 등 21가지 문제가 NP 완전임을 보였고, 지금은 수천 가지가 알려져 있어요. 외판원 문제의 결정 형태("길이 L 이하로 모든 도시를 도는 길이 있는가"), 크기를 키운 일반 스도쿠, 지뢰 찾기 판이 앞뒤가 맞는지 판단하는 문제도 NP 완전이에요. 이 문제들은 하나라도 빠르게 풀리면 전부 빠르게 풀리는 운명 공동체예요.

P와 NP가 같은지는 아직 아무도 몰라요. 2000년 클레이 수학 연구소가 상금 100만 달러를 걸고 고른 일곱 문제 중 하나예요. 대부분의 연구자는 P ≠ NP, 즉 확인은 쉬워도 찾기는 본질적으로 어려운 문제가 있다고 믿어요. 만약 P = NP이고 그 방법이 실용적이라면 세상이 크게 바뀌어요. 길이가 적당한 수학 증명도 확인하듯 쉽게 찾게 되고, 많은 암호가 무너져요. 암호는 "비밀 키를 알면 확인은 쉽지만, 모르면 찾기는 어렵다"는 성질에 기대고 있거든요. 다만 RSA가 기대는 소인수분해는 NP에 속하지만 NP 완전이라고 알려져 있지는 않아서, P ≠ NP가 증명된다고 RSA의 안전이 저절로 보장되지는 않아요.

어려운 문제를 만났을 때

실무에서 NP 완전 문제를 만나는 일은 흔해요. 배송 경로, 근무표, 시간표, 회로 배치, 짐 싣기가 다 그래요. "NP 완전이니 포기"가 아니라 상황에 맞는 전략을 고르면 돼요. 모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 길을 찾는 외판원 문제로 확인해 볼게요.

import math
from itertools import permutations

random.seed(4)
cities = [(random.random() * 100, random.random() * 100) for _ in range(9)]

def tour_length(tour):
    return sum(math.dist(cities[tour[i]], cities[tour[(i + 1) % len(tour)]]) for i in range(len(tour)))

def brute_force():                                   # 0번 도시에서 출발하는 모든 순서: 8! = 40,320가지
    best = min(permutations(range(1, len(cities))), key=lambda p: tour_length((0,) + p))
    return (0,) + best

def nearest_neighbor():                              # 늘 가장 가까운, 아직 안 간 도시로 가요
    tour, left = [0], set(range(1, len(cities)))
    while left:
        nxt = min(left, key=lambda c: math.dist(cities[tour[-1]], cities[c]))
        tour.append(nxt)
        left.remove(nxt)
    return tuple(tour)

def two_opt(tour):                                   # 꼬인 구간을 뒤집어 풀면서 더 줄어들지 않을 때까지
    tour, improved = list(tour), True
    while improved:
        improved = False
        for i in range(1, len(tour) - 1):
            for j in range(i + 1, len(tour)):
                new = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]
                if tour_length(new) < tour_length(tour) - 1e-9:
                    tour, improved = new, True
    return tuple(tour)

best = brute_force()
nn = nearest_neighbor()
for label, tour in [("모든 순서를 다 따진 최적", best), ("가장 가까운 곳부터", nn), ("거기서 꼬인 길 풀기", two_opt(nn))]:
    print(f"{label}: 길이 {tour_length(tour):.1f} (최적의 {tour_length(tour) / tour_length(best):.0%})")
모든 순서를 다 따진 최적: 길이 282.7 (최적의 100%)
가장 가까운 곳부터: 길이 299.5 (최적의 106%)
거기서 꼬인 길 풀기: 길이 282.7 (최적의 100%)

도시가 9개면 0번에서 출발하는 순서가 8! = 40,320가지라 모두 따질 수 있어요. 하지만 20개면 순서가 10경을 넘어요. 가장 가까운 도시부터 가는 탐욕법은 순식간에 최적보다 6% 긴 길을 찾았고, 서로 꼬인 구간을 뒤집어 푸는 2-opt 개선을 더하니 이번에는 최적과 같아졌어요. 이런 방법은 최적을 보장하지 않지만, 도시가 수천 개여도 금방 꽤 좋은 답을 줘요. 어려운 문제를 만났을 때 쓰는 전략을 정리하면 이래요.

  • 입력이 작으면 다 따지기: 9개쯤은 전부 따져도 돼요. 재귀와 동적 계획법 강의의 방법을 쓰면 외판원 문제도 n² × 2ⁿ 정도로 줄어서 스무 개 남짓까지 다룰 수 있어요.
  • 근사 알고리즘: 최적의 몇 배 안쪽이라는 보장이 있는 방법이에요. 예를 들어 거리가 삼각 부등식을 지키는 외판원 문제에는 최적의 1.5배를 넘지 않는 길을 다항 시간에 찾는 방법(크리스토피데스 알고리즘)이 있어요.
  • 휴리스틱: 보장은 없지만 실제로 잘 되는 방법이에요. 위의 탐욕법과 2-opt, 담금질 기법, 유전 알고리즘 같은 것들이에요.
  • 전용 도구에 맡기기: SAT 풀이 프로그램이나 정수 계획법 풀이 프로그램에 문제를 바꿔 넣으면, 최악은 지수 시간이어도 실제 문제는 놀랄 만큼 잘 풀려요. 외판원 문제는 도시 8만 5천여 개짜리를 최적으로 푼 기록도 있어요.
  • 특별한 구조 찾기: NP 완전은 최악의 입력에 대한 이야기예요. 실제 데이터에는 트리 모양이거나 값이 작은 것처럼 쉽게 풀리는 구조가 숨어 있을 때가 많아요. 부분집합의 합도 수가 작으면 동적 계획법으로 (수의 개수 × 목표값)에 비례하는 시간에 풀려요.

더 넓은 지도

  • 시간만큼 메모리도 따질 수 있어요. 메모리를 다항식만큼만 쓰는 문제의 모임을 PSPACE라고 하고, NP를 포함해요. 판 크기를 키운 일반 체스와 바둑은 지수 시간이 꼭 필요하다는 게 증명된 문제예요.
  • 양자 컴퓨터에는 소인수분해를 다항 시간에 하는 쇼어 알고리즘이 있어서, 충분히 큰 양자 컴퓨터가 나오면 RSA와 지금의 타원 곡선 암호가 위험해져요. 그래서 2024년에 미국 표준 기관(NIST)이 양자 컴퓨터로도 풀기 어렵다고 여겨지는 새 공개키 암호 표준을 발표했어요. 하지만 양자 컴퓨터가 NP 완전 문제를 빠르게 푼다는 근거는 없고, 대부분의 연구자는 그렇지 않을 거라고 봐요.

실습

  1. find_subset을 동적 계획법으로 바꿔 보세요. "지금까지의 수로 만들 수 있는 합의 집합"을 하나씩 늘려 가면 돼요. 수가 클 때와 작을 때 어느 쪽 방법이 빠른가요?
  2. 시험 시간표에 "수학과 화학도 같은 학생이 듣는다"는 조건을 더하면 3교시 안에 짤 수 있나요? 안 된다면 그 이유와 필요한 교시 수를 말해 보세요.
  3. coloring_to_sat의 절 수가 정점과 간선의 수에 따라 어떻게 늘어나는지 식으로 써 보세요. 환원이 다항 시간이어야 하는 이유는 무엇일까요?
  4. 도시를 11개로 늘려 brute_force를 돌려 보세요(꽤 오래 걸려요). 가장 가까운 곳부터와 2-opt의 결과는 최적과 얼마나 차이 나나요?
  5. 다 채운 스도쿠 판이 맞는지 확인하는 함수를 만들어 보세요. 확인에 걸리는 시간은 판 크기에 따라 어떻게 늘어나나요?

자주 하는 오해

  • NP는 "다항 시간이 아닌" 문제다. 비결정적 다항 시간의 줄임말이에요. P도 NP에 들어가요.
  • NP 완전 문제는 풀 수 없다. 풀 수는 있어요. 최악의 경우에 빠른 방법이 알려져 있지 않을 뿐이고, 실제 입력은 잘 풀릴 때가 많아요.
  • 컴퓨터가 빨라지면 해결된다. 2ⁿ에서는 컴퓨터가 1,000배 빨라져도 다룰 수 있는 n이 10쯤 늘 뿐이에요.
  • 양자 컴퓨터는 모든 어려운 문제를 푼다. 소인수분해 같은 특정 문제에는 강하지만, NP 완전 문제를 빠르게 푼다는 근거는 없어요.
  • 다항 시간이면 늘 실용적이다. n¹⁰⁰은 다항식이지만 쓸 수 없어요. 다항 시간은 기준일 뿐, 실제로는 지수와 상수를 함께 봐야 해요.

점검 문제

  1. 이론에서 "빠른" 알고리즘을 다항 시간으로 정하는 이유는?
  2. P와 NP는 각각 어떤 문제의 모임인가요?
  3. 부분집합의 합이 NP에 속하는 이유는?
  4. 환원이란 무엇이고, 시험 시간표 문제를 어떻게 SAT로 바꿨나요?
  5. NP 완전이란 무엇이고, SAT가 NP 완전인 이유를 한마디로 하면?
  6. P = NP라면 암호에는 어떤 일이 생길 수 있나요?
  7. NP 완전 문제를 실무에서 만났을 때 쓸 수 있는 전략 세 가지는?
  8. 양자 컴퓨터는 어떤 문제에 위협이 되고, 어떤 문제에는 그렇다고 보기 어려운가요?

정답

  1. 실제로 발견되는 다항 시간 알고리즘은 대개 지수가 작고, 컴퓨터나 계산 모델을 바꿔도 다항식은 다항식으로 남아서 문제 자체의 성질로 다루기 좋기 때문이에요.
  2. P는 다항 시간에 풀 수 있는 문제, NP는 답(증거)이 주어지면 맞는지를 다항 시간에 확인할 수 있는 문제의 모임이에요.
  3. 부분집합이 답으로 주어지면 그 수들을 더해 목표값과 같은지 보기만 하면 되니, 다항 시간에 확인할 수 있기 때문이에요.
  4. 문제 A를 문제 B로 바꿔서 B의 풀이로 A를 푸는 거예요. "과목 v가 시간대 c다"를 변수로 두고, 과목마다 시간대가 하나이고 겹치는 과목끼리는 시간대가 달라야 한다는 규칙을 논리식의 절로 바꿨어요.
  5. NP에 속하면서 NP의 모든 문제가 다항 시간에 환원되는 문제예요. SAT는 어떤 NP 문제든 그 답을 확인하는 프로그램이 돌아가는 과정을 논리식으로 옮길 수 있어서 NP 완전이에요.
  6. 암호는 키를 알면 확인은 쉽고 모르면 찾기 어렵다는 성질에 기대는데, P = NP이고 그 방법이 실용적이라면 확인이 쉬운 것은 찾기도 쉬워져서 많은 암호가 무너질 수 있어요.
  7. 입력이 작으면 다 따지거나 동적 계획법을 쓰고, 최적의 몇 배 안쪽을 보장하는 근사 알고리즘이나 실제로 잘 되는 휴리스틱을 쓰고, SAT나 정수 계획법 풀이 프로그램에 맡기거나 데이터의 특별한 구조를 이용해요.
  8. 소인수분해와 이산 로그를 빠르게 푸는 쇼어 알고리즘 때문에 RSA와 타원 곡선 암호에는 위협이 돼요. 하지만 NP 완전 문제를 빠르게 푼다는 근거는 없어요.

다음 강의

컴퓨터 과학 이론 트랙을 마쳤어요. 스위치로 덧셈기를 만들고, 오토마타에서 문법과 튜링 기계로 올라가, 계산할 수 없는 문제와 빠르게 풀기 어려운 문제의 경계까지 봤어요. 다음은 컴퓨터 과학 심화 트랙이에요. 이론에서 실제 기계로 돌아와, 같은 O(n)인데도 수십 배 빠르게 만드는 캐시와 파이프라인, 메모리 계층부터 시작해요.