NP 클래스

NP 클래스는 답이 맞는지 빨리 확인할 수 있는 문제들을 한 모임으로 묶습니다. 답을 찾는 데 얼마나 걸리는지는 따지지 않습니다. 쉬운 문제와 어려운 문제가 함께 듭니다. 이 모임이 빨리 풀리는 문제의 모임과 같은지는 아직 아무도 모릅니다.

상세

네 자리 번호 자물쇠가 있다고 합시다. 번호를 모르면 0000 부터 하나씩 돌려 봐야 합니다. 누가 번호를 알려 주면 한 번 맞춰 보고 열리는지만 보면 됩니다. 찾는 일과 확인하는 일의 수고가 이렇게 다릅니다.

NP(Nondeterministic Polynomial time, 비결정적 다항 시간) 클래스는 이 차이를 문제의 모임으로 옮긴 이름입니다. 여기서 클래스는 프로그래밍의 클래스가 아니라 문제를 한데 모은 모임을 뜻합니다. 「비결정적」이라는 이름의 뜻은 뒤 소절에서 풉니다.

이 절은 정의에 드는 낱말 셋을 먼저 풉니다. 결정 문제, 다항 시간, 근거와 검증기입니다. 그다음 정의를 세우고 부분집합 합 문제로 확인 과정을 직접 봅니다. 끝으로 이웃한 모임과의 관계, 백엔드에서 이 이름을 만나는 곳, 흔한 오해를 차례로 봅니다.

결정 문제

결정 문제는 답이 「예」나 「아니요」인 문제입니다. 「이 목록에 7 이 있나」가 결정 문제입니다. NP 클래스에는 결정 문제만 듭니다. 답의 꼴을 하나로 맞춰 두어야 서로 다른 문제끼리 어려움을 견줄 수 있기 때문입니다.

「가장 짧은 경로를 구하라」처럼 가장 작거나 큰 값을 구하는 문제는 최적화 문제라고 부릅니다. 이런 문제도 「길이 k 이하인 경로가 있나」로 바꿔 물으면 결정 문제가 됩니다. 이렇게 바꾼 물음을 그 문제의 결정판이라고 부릅니다.

다항 시간

다항 시간은 입력 크기 n 에 대해 n², n³ 처럼 n 을 정해진 횟수만큼 곱한 값을 넘지 않는 시간입니다. 입력이 두 배가 되어도 시간은 정해진 배수로만 늡니다. 그래서 다항 시간은 컴퓨터로 감당할 수 있는 일의 경계로 흔히 쓰입니다.

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

20 ** 3   # 8000
60 ** 3   # 216000
2 ** 20   # 약 100만
2 ** 60   # 약 115경

n 이 20 에서 60 으로 세 배가 되면 n³ 은 27 배가 됩니다. 2ⁿ 은 1조 배쯤 커집니다. NP 클래스의 정의에서 「빨리」는 언제나 다항 시간을 뜻합니다.

근거와 검증기

근거는 답이 「예」라는 것을 보여 주는 증거물입니다. 「합을 9 로 만들 수 있나」에서는 고른 수 묶음이 근거입니다. 근거가 있으면 「예」라는 주장을 말로 믿을 필요 없이 직접 따져 볼 수 있습니다.

검증기는 입력과 근거를 함께 받아 그 근거가 맞는지 판정하는 프로그램입니다. 판정은 「맞다」나 「아니다」 둘 중 하나입니다. 검증기는 근거를 찾지 않습니다. 받은 근거를 따져 보기만 합니다.

NP 클래스의 정의

NP 클래스는 결정 문제의 모임입니다. 결정 문제 X 가 아래 세 조건을 채우는 검증기를 가지면 X 는 NP 에 듭니다.

1. 검증기가 다항 시간 안에 판정을 끝냅니다
2. 답이 「예」인 입력에는 검증기가 「맞다」고 하는 근거가 하나 이상 있습니다
3. 답이 「아니요」인 입력에는 검증기가 「맞다」고 하는 근거가 하나도 없습니다

근거의 길이에도 한도가 있습니다. n², n³ 처럼 입력 크기로 정해진 길이를 넘으면 안 됩니다. 조건 1 이 검증기가 일하는 시간을 묶는다면 이 한도는 내미는 근거의 크기를 묶습니다. 근거가 지나치게 길면 받아 읽기만 해도 다항 시간을 넘기기 때문입니다.

이 정의는 답을 찾는 방법을 하나도 묻지 않습니다. 근거가 어디서 왔는지도 묻지 않습니다. 확인이 다항 시간에 끝난다는 것 하나만 요구합니다.

부분집합 합 문제로 보는 확인

부분집합 합 문제는 수 목록에서 몇 개를 골라 합을 목표값으로 만들 수 있는지 묻습니다. 목록이 [3, 34, 4, 12, 5, 2] 이고 목표값이 9 라고 합시다. 근거는 고른 수 묶음입니다. 검증기는 이렇게 짭니다.

def verify(nums, target, pick):
    ok = all(pick.count(x) <= nums.count(x)
             for x in pick)
    return ok and 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ⁿ 개입니다. 이 문제를 다항 시간에 푸는 방법은 아직 알려지지 않았습니다.

아래 그림은 목록에서 3, 4, 5 세 수만 골라 갈림길을 그린 것입니다. 갈림길마다 「이 수를 넣나 빼나」를 정하므로 갈래가 한 층마다 두 배로 늡니다.

flowchart TD
    R["3 을 넣나"]
    R -->|넣는다| A1["4 를 넣나"]
    R -->|뺀다| A2["4 를 넣나"]
    A1 -->|넣는다| B1["5 를 넣나"]
    A1 -->|뺀다| B2["5 를 넣나"]
    A2 -->|넣는다| B3["5 를 넣나"]
    A2 -->|뺀다| B4["5 를 넣나"]
    B1 -->|넣는다| L1["3·4·5<br>합 12"]
    B1 -->|뺀다| L2["3·4<br>합 7"]
    B2 -->|넣는다| L3["3·5<br>합 8"]
    B2 -->|뺀다| L4["3<br>합 3"]
    B3 -->|넣는다| L5["4·5<br>합 9"]
    B3 -->|뺀다| L6["4<br>합 4"]
    B4 -->|넣는다| L7["5<br>합 5"]
    B4 -->|뺀다| L8["없음<br>합 0"]
    L5 ~~~ N["34 · 12 · 2 도 같은 식으로 갈린다 · 모두 64갈래<br>「예」는 굵은 길 하나로 보인다<br>「아니요」는 64갈래 끝을 전부 봐야 한다"]
    class R,A2,B3,L5 hit
    classDef hit stroke-width:3px
    linkStyle 1,4,10 stroke-width:3px

굵게 그린 길은 3 을 빼고 4 와 5 를 넣은 기록입니다. 갈림길마다 고른 쪽을 이어 적은 이 기록이 곧 근거 [4, 5] 입니다.

확인은 다항 시간에 끝나도 지금 아는 방법으로는 찾는 데 지수 시간이 드는 문제입니다. NP 클래스가 붙잡으려는 문제의 전형이 이렇습니다.

「예」와 「아니요」의 비대칭

정의는 「예」인 경우의 근거만 요구합니다. 「아니요」를 빨리 확인하라는 요구는 없습니다. 그래서 「아니요」를 빨리 확인할 길이 없는 문제도 NP 에 들 수 있습니다.

부분집합 합에서 답이 「아니요」라면 「합을 맞추는 묶음이 없다」를 보이려고 무엇을 내밀어야 할까요. 짧게 확인되는 근거는 알려져 있지 않습니다. 위 그림으로 치면 굵은 길 하나가 아니라 갈래 끝을 전부 보여야 합니다.

「아니요」를 빨리 확인할 수 있는 결정 문제의 모임은 따로 co-NP라고 부릅니다. NP 와 co-NP 가 같은 모임인지도 아직 밝혀지지 않았습니다.

이름 속의 비결정적 기계

비결정적 튜링 기계는 갈림길을 만나면 맞는 쪽을 알아서 골라 가는 가상의 계산 기계입니다. 실제로 만들 수 있는 기계가 아닙니다. 어려움을 견주려고 세운 이론 속 기계입니다. NP 는 원래 이 기계가 다항 시간에 푸는 결정 문제의 모임으로 정의됐습니다.

이 정의는 검증기 정의와 같은 모임을 가리킵니다. 앞의 부분집합 합 그림에서 갈림길은 「이 수를 넣나 빼나」였습니다. 기계가 갈림길마다 고른 길을 적어 두면 그 기록이 근거가 됩니다. 근거가 있으면 기계는 갈림길마다 근거가 가리키는 쪽을 고르면 됩니다.

P 와 NP

P(Polynomial time, 다항 시간)는 다항 시간 안에 푸는 방법이 있는 결정 문제의 모임입니다. 「정렬된 목록에 값 x 가 있나」는 반씩 나눠 찾으면 금방 답이 나오므로 P 에 듭니다.

P 의 문제는 모두 NP 에도 듭니다. 근거를 받을 필요도 없이 처음부터 풀어 버리면 확인이 끝나기 때문입니다. 검증기가 근거를 무시하고 문제를 직접 풀면 됩니다.

NP 의 문제가 모두 P 에 드는지는 아무도 증명하지 못했습니다. 「다항 시간에 확인되는 문제는 다항 시간에 찾을 수도 있나」라는 이 물음이 P 대 NP 문제입니다. 연구자 대부분은 두 모임이 다르다고 봅니다.

NP-완전과 NP-난해

NP 안의 문제끼리 어려움을 견주려면 한 문제를 다른 문제로 바꿔 푸는 방법이 있어야 합니다. 이 소절은 그 방법을 먼저 풀고 그 위에서 NP-완전과 NP-난해를 차례로 정합니다.

환원은 문제 X 의 입력을 문제 C 의 입력으로 바꾼 뒤 C 를 풀어 X 의 답을 얻는 일입니다. C 의 답 「예·아니요」를 X 의 답으로 그대로 씁니다. 여기서는 바꾸는 일도 다항 시간에 끝나야 합니다. 바꾸는 데 오래 걸리면 C 가 빨리 풀려도 X 는 빨리 풀리지 않기 때문입니다.

NP-완전은 NP 안에 들면서 NP 의 모든 문제가 자기에게 환원되는 문제입니다. NP 안에서 가장 어려운 문제들이라고 풀어 말합니다. 앞에서 본 부분집합 합 문제가 NP-완전입니다.

NP-완전 문제 하나만 다항 시간에 풀려도 NP 전체가 다항 시간에 풀립니다. 아래 그림의 순서를 따라가면 그 까닭이 보입니다. 바꾸는 데 다항 시간, C 를 푸는 데 다항 시간이면 둘을 이어도 다항 시간입니다.

flowchart TD
    X["NP 의 아무 문제 X 의 입력"] --> T["다항 시간에 바꾼다"]
    T --> CI["NP-완전 문제 C 의 입력"]
    CI --> S["C 를 푼다"]
    S --> A["예 · 아니요<br>X 의 답으로 그대로 쓴다"]
    S -.->|"C 가 다항 시간에 풀리면"| F["X 도 다항 시간에 풀린다"]

NP-난해 문제는 NP 의 모든 문제가 자기에게 환원되기만 하면 됩니다. NP-완전과 달리 NP 에 드는지는 따지지 않습니다. 그래서 NP-난해 문제는 NP 밖에 있을 수도 있습니다. NP-완전 문제는 NP-난해이면서 NP 에도 드는 문제입니다.

외판원 순회는 모든 도시를 한 번씩 도는 가장 짧은 순회를 찾는 문제입니다. 원래 물음은 순회 자체를 내놓으라고 하는 최적화 문제라서 답이 「예·아니요」가 아닙니다. 최적화 문제로 물은 이 원래 판을 최적화판이라고 부릅니다. 최적화판은 NP 에 넣을 수 없지만 NP-난해에 듭니다.

「길이 k 이하인 순회가 있나」로 바꾼 결정판은 NP 에 듭니다. 이 결정판은 NP-완전이기도 합니다.

P 와 NP 가 다르다고 믿을 때 NP 안을 그리면 아래와 같습니다. 바깥 상자가 NP 입니다. P 와 NP-완전은 그 안에서 서로 겹치지 않습니다.

flowchart TD
    subgraph NP["NP · 답을 빨리 확인할 수 있는 결정 문제"]
        P["P · 빨리 풀리는 결정 문제<br>정렬된 목록에서 값 찾기"]
        C["NP-완전 · NP 안에서 가장 어려운 문제<br>부분집합 합 문제 · 외판원 순회 결정판"]
    end

백엔드에서 만나는 NP 문제

회의 시간표 짜기, 서로 충돌하는 옵션을 피해 설정 고르기, 서버마다 용량 안에서 작업 나눠 싣기가 NP 의 문제입니다. 셋은 차례로 그래프 색칠, SAT(Boolean satisfiability, 불리언 만족 가능성 문제), 빈 패킹이라는 이름으로 알려져 있습니다. 셋 다 결정판으로 바꿔 물으면 근거를 받았을 때 확인이 금방 끝납니다. 셋 다 큰 입력에서 정답을 빨리 찾는 방법은 알려져 있지 않습니다.

그래서 큰 입력에서는 정답을 고집하지 않습니다. 근사 알고리즘이나 휴리스틱으로 쓸 만한 답을 빨리 내는 쪽을 고릅니다.

다항 시간에 확인된다는 성질은 여기서 쓸모가 있습니다. 외부 풀이 프로그램이나 휴리스틱이 내놓은 답이 조건을 지키는지는 다항 시간에 따져 볼 수 있습니다. 답을 만든 쪽을 믿지 않아도 검증기 하나로 걸러 낼 수 있습니다.

큰 수를 소수의 곱으로 나누는 소인수분해도 확인이 쉬운 문제입니다. 결정판은 「이 수에 1 보다 크고 k 보다 작은 인수가 있나」를 묻습니다. 그 인수를 근거로 받으면 나눠 보기만 하면 확인이 끝납니다. 그래서 결정판이 NP 에 듭니다.

공개 키 암호의 일부 방식은 이 확인과 찾기의 차이로 안전성을 얻습니다. 인수를 받으면 확인은 금방 끝납니다. 큰 수에서 인수를 찾는 일은 지금 아는 방법으로는 다항 시간에 끝나지 않습니다. P 와 NP 가 같다고 밝혀지면 이론상 소인수분해도 다항 시간에 풀립니다.

흔한 오해

NP 라는 이름은 자주 잘못 읽힙니다. 아래는 그 오해와 바른 읽기입니다.

셋째 줄은 NP 의 문제가 모두 풀리는 문제라는 뜻입니다. 어떤 알고리즘으로도 못 푸는 정지 문제와는 다른 종류의 어려움입니다. NP 에서 따지는 것은 풀리느냐가 아니라 얼마나 빨리 풀리느냐입니다.

관련 항목

NP 클래스가 속하는 상위 분류

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

NP 클래스를 정의하는 데 쓰이는 개념

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

NP 클래스와 포함 관계로 엮이는 복잡도 클래스

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

NP 클래스를 둘러싼 정리와 미해결 문제

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

NP 클래스에 드는 대표 결정 문제

부분집합 합 문제 · SAT · 3-SAT · 그래프 색칠 · 해밀턴 순환 · 외판원 순회 · 배낭 문제 · 소인수분해 · 그래프 동형 문제

NP 클래스의 문제 앞에서 고르는 풀이 방법

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

NP 클래스의 성질에 기대는 응용

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