P 대 NP

P 대 NP 는 답이 맞는지 빨리 확인할 수 있는 문제라면 답을 빨리 찾을 수도 있는지 묻습니다. 컴퓨터 과학에서 가장 유명한 미해결 문제입니다. 연구자 대부분은 찾는 일이 확인하는 일보다 본질적으로 어렵다고 봅니다. 그러나 이것을 증명한 사람은 아직 없습니다.

상세

친구가 다 푼 스도쿠를 건넨다고 합시다. 가로줄과 세로줄, 작은 상자를 한 번씩 훑으면 맞게 풀었는지 금방 압니다. 빈 판을 받아 직접 채우려면 숫자를 넣어 보고 막히면 지우기를 되풀이해야 합니다.

P 대 NP 는 이 수고의 차이가 피할 수 없는 것인지 묻습니다. 확인이 쉬운 문제라면 푸는 방법도 언제나 쉽게 만들 수 있는지 묻는 것입니다. 아니면 확인만 쉽고 찾기는 본질적으로 어려운 문제가 있는지를 묻는 것입니다.

이 절은 물음에 드는 낱말부터 차례로 풉니다. 그다음 물음을 정확한 꼴로 세웁니다. 이어서 물음 전체의 열쇠를 쥔 문제들을 봅니다. 끝으로 두 가지 답이 각각 무엇을 바꾸는지, 왜 아직 못 풀었는지, 백엔드 개발자가 이 물음을 어디서 만나는지 봅니다.

결정 문제

결정 문제는 답이 「예」나 「아니요」 하나로 끝나는 문제입니다. 「이 목록에 7 이 있나」가 결정 문제입니다. P 대 NP 는 결정 문제만 놓고 따집니다. 답의 꼴을 하나로 맞춰야 서로 다른 문제의 어려움을 견줄 수 있기 때문입니다.

「가장 짧은 경로를 구하라」처럼 값을 내놓으라는 문제도 결정 문제로 바꿀 수 있습니다. 「길이가 100 이하인 경로가 있나」로 물으면 됩니다. 이렇게 바꾼 물음을 원래 문제의 결정판이라고 부릅니다.

다항 시간

다항 시간은 입력 크기 n 에 대해 n², n³ 처럼 n 의 거듭제곱 꼴로 묶이는 시간입니다. 입력이 두 배가 되어도 걸리는 시간은 정해진 배수만큼만 늡니다. 그래서 이 분야에서는 「다항 시간에 풀린다」를 「빨리 풀린다」와 같은 뜻으로 씁니다.

반대편에는 지수 시간이 있습니다. 2ⁿ 처럼 n 이 하나 늘 때마다 시간이 곱절이 됩니다. n 이 20 일 때와 60 일 때 일의 양을 견주면 이렇습니다.

20 ** 3     # 8000
2 ** 20     # 1048576
60 ** 3     # 216000
2 ** 60     # 약 115경

n 이 세 배가 되는 동안 n³ 은 27 배가 됩니다. 2ⁿ 은 1조 배 넘게 커집니다. 이 문서에서 「빨리」는 언제나 다항 시간을 뜻합니다.

P 클래스

P(Polynomial time, 다항 시간)는 다항 시간에 푸는 방법이 있는 결정 문제를 모두 모은 것입니다. 이렇게 성질이 같은 문제를 모은 것을 클래스라고 부릅니다. 「정렬된 목록에 7 이 있나」는 반씩 잘라 찾으면 금방 끝나므로 P 에 듭니다. 「그래프의 두 정점이 이어져 있나」도 그래프를 한 번 훑으면 되므로 P 에 듭니다.

NP 클래스

NP 의 정의를 읽으려면 증거부터 알아야 합니다. 증거는 답이 「예」라는 주장을 뒷받침하는 물건입니다. 스도쿠라면 다 채운 판이 증거입니다.

NP(Nondeterministic Polynomial time, 비결정적 다항 시간 — 이름 풀이는 이 소절 끝에)는 답이 「예」일 때 그 증거를 받으면 다항 시간에 확인할 수 있는 결정 문제의 클래스입니다. 증거를 어떻게 찾는지는 묻지 않습니다. 받은 증거를 따져 보는 일이 빨리 끝나기만 하면 됩니다.

증거를 받아 맞는지 판정하는 프로그램을 검증기라고 부릅니다. NP 에 드는 문제에는 다항 시간에 끝나는 검증기가 있습니다.

부분집합 합 문제로 확인해 봅시다. 수 목록에서 몇 개를 골라 합을 목표값으로 만들 수 있는지 묻는 문제입니다. 증거는 고른 수 묶음입니다. 검증기는 이렇게 짭니다.

def verify(nums, target, pick):
    for x in set(pick):
        if pick.count(x) > nums.count(x):
            return False
    return sum(pick) == target

nums = [3, 34, 4, 12, 5, 2]
verify(nums, 9, [4, 5])     # True
verify(nums, 9, [3, 4])     # False
verify(nums, 9, [4, 4, 1])  # False

검증기는 고른 수가 목록에 있는지와 합이 맞는지만 봅니다. 마지막 줄은 하나뿐인 4 를 두 번 쓰고 없는 1 을 넣어서 거절됩니다. 목록과 증거를 몇 번 훑으면 끝나므로 확인은 다항 시간입니다.

증거 없이 답을 찾으려면 사정이 다릅니다. 원소가 n 개면 고를 수 있는 묶음이 2ⁿ 개입니다. 이 문제를 다항 시간에 푸는 방법은 아직 알려지지 않았습니다.

NP 의 N 은 「아님(Not)」이 아닙니다. 처음 정의가 갈림길마다 맞는 쪽을 알아서 골라 가는 가상의 기계로 세워져서 붙은 이름입니다. 이 기계를 비결정적 튜링 기계라고 부릅니다. 두 정의는 같은 클래스를 가리킵니다. 실무에서는 검증기 쪽 정의가 훨씬 손에 잡힙니다.

P 와 NP 의 포함 관계

P 의 문제는 모두 NP 에도 듭니다. 증거를 받을 필요 없이 처음부터 풀어 버리면 확인도 끝나기 때문입니다. 그래서 P 는 NP 안에 들어 있습니다.

남은 것은 거꾸로의 물음입니다. NP 의 문제도 모두 P 에 드는지, 다시 말해 두 클래스가 같은지입니다. 이것을 짧게 「P = NP 인가」라고 적습니다. 확인이 다항 시간에 되는 문제라면 푸는 것도 언제나 다항 시간에 되는지를 묻는 것입니다.

환원

물음의 열쇠를 쥔 문제들을 보려면 환원부터 알아야 합니다. 환원은 문제 A 를 문제 B 로 바꿔 푸는 일입니다. A 의 입력을 B 의 입력으로 고쳐 씁니다. 그리고 B 의 답을 A 의 답으로 씁니다.

미로 찾기를 예로 들어 봅시다. 칸을 정점으로, 이웃한 칸 사이를 선으로 옮겨 적으면 「출구까지 길이 있나」가 「두 정점이 이어져 있나」로 바뀝니다. 그러면 그래프를 훑는 방법으로 미로를 풉니다.

고쳐 쓰는 일이 다항 시간에 끝나면, B 를 빨리 푸는 방법이 곧 A 를 빨리 푸는 방법이 됩니다. 그래서 A 를 B 로 환원할 수 있으면 B 는 적어도 A 만큼 어렵다고 말합니다.

NP-완전

NP-완전은 NP 에 들면서 NP 의 모든 문제가 자기에게로 환원되는 문제입니다. NP 안에서 가장 어려운 문제들이라고 풀어 말합니다. 외판원 순회의 결정판, 부분집합 합 문제, 그래프 색칠이 여기 듭니다.

처음으로 NP-완전임이 밝혀진 문제는 논리식을 참으로 만드는 값이 있는지 묻는 불 만족성 문제(Boolean Satisfiability, 줄여서 SAT)입니다. 이것을 보인 정리를 쿡-레빈 정리라고 부릅니다.

그 뒤로는 SAT 가 출발점이 되었습니다. NP 에 드는 문제 X 가 있을 때 SAT 를 X 로 환원해 보이면 X 도 NP-완전이 됩니다. NP 의 모든 문제는 이미 SAT 로 환원됩니다. 그러니 SAT 를 거쳐 X 로도 환원되는 것입니다.

NP-완전 문제 하나만 다항 시간에 풀려도 NP 전체가 다항 시간에 풀립니다. 거꾸로 그중 하나라도 다항 시간에 못 푼다는 것이 증명되면 P 와 NP 는 다릅니다. 물음 전체가 이 문제들 가운데 아무거나 하나에 걸려 있는 셈입니다.

두 가지 답

답은 둘 중 하나입니다. 두 경우에 P, NP, NP-완전이 놓이는 모양을 그리면 아래와 같습니다.

flowchart TD
    subgraph DIFF["P 와 NP 가 다르다면 · 연구자 대부분의 예상"]
        subgraph NP1["NP · 답을 빨리 확인할 수 있는 문제"]
            P1["P · 빨리 풀리는 문제"]
            C1["NP-완전 · NP 에서 가장 어려운 문제"]
        end
    end
    subgraph SAME["P 와 NP 가 같다면"]
        A2["P = NP · NP-완전도 같은 덩어리에 든다"]
    end
    DIFF ~~~ SAME

위 칸에서는 P 와 NP-완전이 NP 안에서 서로 떨어져 있습니다. 아래 칸에서는 확인할 수 있는 문제를 모두 풀 수도 있게 되어 세 이름이 한 덩어리가 됩니다.

두 경우가 실무에 무엇을 바꾸는지 견주면 이렇습니다.

둘째 줄이 백엔드 개발자에게 가장 가깝습니다. 아래 「백엔드에서 만나는 장면」 소절에서 다시 봅니다.

아직 못 푼 까닭

P 와 NP 가 다르다는 것을 보이려면 「NP-완전 문제를 다항 시간에 푸는 방법은 없다」를 증명해야 합니다. 지금까지 나온 방법만이 아니라 앞으로 누가 만들 수 있는 모든 방법에 대해서입니다. 「아직 못 찾았다」와 「있을 수 없다」 사이의 거리가 이 물음의 어려움입니다.

같다는 쪽도 막혀 있습니다. 같다면 NP-완전 문제 하나를 다항 시간에 푸는 방법만 내놓으면 끝납니다. 오랫동안 많은 사람이 시도했지만 아무도 찾지 못했습니다. 연구자 대부분이 「다르다」 쪽에 서는 까닭이 이 경험입니다.

이 물음은 클레이 수학연구소가 상금을 걸어 둔 밀레니엄 문제 일곱 가운데 하나입니다. 풀면 백만 달러를 받습니다.

백엔드에서 만나는 장면

백엔드 개발자가 P 대 NP 를 직접 풀 일은 없습니다. 대신 이 물음이 남긴 결과를 빌려 쓰는 일은 자주 있습니다. 두 장면을 봅니다.

첫째는 요구가 NP-완전 문제로 밝혀질 때입니다. 회의실 배정, 배송 경로 짜기, 서버마다 용량 안에서 작업 나눠 싣기가 흔히 그렇습니다. 이때 큰 입력에서 정답을 빨리 내는 방법을 찾는 것은 P 대 NP 를 푸는 일과 같습니다. 그래서 설계를 다른 방향으로 돌립니다.

돌리는 방향은 대개 셋입니다.

어느 쪽이든 정답과 응답 시간 가운데 하나를 양보하는 선택입니다. 요구가 NP-완전이라는 것을 먼저 알아보면 다항 시간에 정답을 내는 방법을 찾느라 시간을 쓰지 않아도 됩니다.

둘째는 암호입니다. 공개 키 암호는 확인은 쉽고 찾기는 어려운 일에 안전을 맡깁니다. 큰 수를 두 소수로 나누는 소인수분해가 그렇습니다. 두 소수를 받으면 곱해 보기만 하면 됩니다. 곱만 보고 두 소수를 찾는 다항 시간 방법은 알려지지 않았습니다.

소인수분해의 결정판은 「N 에 1 보다 크고 k 보다 작은 약수가 있나」입니다. 약수 하나를 증거로 받으면 나눠 보기만 하면 되므로 이 물음은 NP 에 듭니다.

예·아니요 답만으로도 약수를 찾을 수 있습니다. k 를 반씩 좁혀 가며 되풀이해 물으면 가장 작은 약수가 나옵니다. 묻는 횟수는 N 의 자릿수에 비례하는 정도입니다. 그러니 P 와 NP 가 같다면 약수를 찾는 일도 이론상 다항 시간에 됩니다.

거꾸로 P 와 NP 가 다르다고 해서 암호가 안전해지지는 않습니다. 소인수분해는 NP-완전이라고 알려져 있지 않습니다. 그래서 P 와 NP 가 달라도 소인수분해만은 다항 시간에 풀릴 가능성이 남습니다.

흔한 오해

이 물음은 이름이 짧아 자주 잘못 읽힙니다. 자주 보는 오해를 바른 읽기와 나란히 놓습니다.

셋째 줄은 어떤 방법으로도 못 푸는 정지 문제와 다르다는 뜻입니다. P 대 NP 가 따지는 것은 풀리느냐가 아니라 얼마나 빨리 풀리느냐입니다.

관련 항목

P 대 NP 가 속하는 상위 분류

계산 복잡도 이론 · 복잡도 클래스 · 계산 이론 · 알고리즘 분석 · 알고리즘

P 대 NP 를 세우는 데 쓰이는 개념

결정 문제 · 최적화 문제 · 다항 시간 · 지수 시간 · 검증기 · 튜링 기계 · 비결정적 튜링 기계 · 시간 복잡도 · 빅오 표기법

P 대 NP 가 견주는 복잡도 클래스

P 클래스 · NP 클래스 · co-NP · NP-완전 · NP-난해 · NP-중간 · PSPACE · EXPTIME

P 대 NP 를 둘러싼 정리와 미해결 문제

환원 · 다항 시간 환원 · 쿡-레빈 정리 · 래드너 정리 · 정지 문제 · 밀레니엄 문제 · NP 대 co-NP

답이 걸려 있는 대표 NP-완전 문제

SAT · 3-SAT · 부분집합 합 문제 · 외판원 순회 · 그래프 색칠 · 해밀턴 순환 · 배낭 문제 · 스도쿠

NP-완전 문제 앞에서 고르는 풀이 방법

완전 탐색 · 백트래킹 · 동적 계획법 · 근사 알고리즘 · 휴리스틱 · SAT 풀이기 · 정수 선형 계획법

P 대 NP 의 답에 기대는 응용

공개 키 암호 · RSA · 일방향 함수 · 소인수분해 · 영지식 증명