NP-완전

NP-완전은 서로 바꿔 풀 수 있는 어려운 문제들을 한 무리로 묶어 줍니다. 그래서 하나를 빨리 푸는 방법은 곧 전부를 빨리 푸는 방법이 됩니다. 회의 시간표 짜기처럼 답이 맞는지 확인하기는 쉬운 문제들이 여기 듭니다. 하지만 답을 빨리 구하는 방법은 아직 아무도 모릅니다.

상세

같은 수수께끼가 백 가지 언어로 적혀 있다고 합시다. 어느 언어판이든 다른 언어로 옮겨 적을 수 있습니다. 그러면 한 언어판만 풀어도 백 개가 모두 풀립니다. 그런데 아직 어느 판도 푼 사람이 없습니다.

NP-완전은 이 생각을 문제에 옮긴 이름입니다. 비유의 백 개 언어판이 NP-완전 무리에 해당합니다. 이 무리는 더 큰 모임 안에 있습니다. 「답을 빨리 확인할 수 있는 문제」를 모두 모은 모임으로, NP(Nondeterministic Polynomial time, 비결정적 다항 시간)라고 부릅니다.

NP 의 어느 문제든 옮겨 적어 받을 수 있는 문제가 NP-완전 문제입니다. 이 「옮겨 적기」와 이름의 「비결정적」은 아래 소절에서 차례로 풉니다.

이 절은 정의에 드는 낱말 넷(결정 문제, 다항 시간, NP, 환원)을 먼저 풀고 NP-완전을 정의합니다.

결정 문제

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

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

외판원 순회가 그런 예입니다. 도시를 모두 한 번씩 들르고 돌아오는 가장 짧은 길을 찾는 문제입니다. 「외판원 순회는 NP-완전이다」라고 할 때는 「길이 k 이하인 순회가 있나」라는 결정판을 말합니다.

다항 시간과 지수 시간

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

반대편에는 지수 시간이 있습니다. 2ⁿ 처럼 n 이 하나 늘 때마다 시간이 두 배가 됩니다. 후보를 2ⁿ 개 모두 확인한다면 n 에 따라 일의 양이 이렇게 늡니다.

2 ** 20   # 약 100만
2 ** 40   # 약 1조
2 ** 60   # 약 115경

입력이 스무 개 늘 때마다 일이 백만 배쯤 늡니다. 입력이 조금만 커져도 감당할 수 없습니다.

P 와 NP

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

NP는 답이 「예」일 때 그 근거를 받으면, 근거가 맞는지 다항 시간 안에 확인할 수 있는 결정 문제의 모임입니다. 답을 찾는 데 걸리는 시간은 따지지 않습니다. 확인만 빠르면 됩니다.

부분집합 합 문제가 NP 의 대표입니다. 수 목록 [3, 34, 4, 12, 5, 2] 에서 몇 개를 골라 합을 9 로 만들 수 있는지 묻습니다. 누가 「4 와 5」라는 근거를 건네면 확인은 두 줄이면 끝납니다.

nums = [3, 34, 4, 12, 5, 2]
pick = [4, 5]                 # 받은 근거
all(x in nums for x in pick)  # True
sum(pick) == 9                # True

이름의 「비결정적」은 NP 를 다르게 정의하는 방식에서 왔습니다. 갈림길마다 맞는 쪽을 알아맞히는 가상의 기계를 두고, 그 기계가 다항 시간에 「예」에 닿는 문제를 모읍니다. 알아맞힌 갈림길들이 곧 근거라서 두 정의는 같은 모임을 가리킵니다. 이 문서는 근거를 확인하는 쪽으로만 설명합니다.

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

P 의 문제는 모두 NP 에도 듭니다. 근거 없이 처음부터 풀어 버리면 확인도 끝나기 때문입니다. 거꾸로 NP 의 문제가 모두 P 에 드는지는 아무도 증명하지 못했습니다. 이 물음이 P 대 NP 문제입니다.

문제를 바꿔 푸는 환원

문제 A 를 풀고 싶습니다. 손에는 문제 B 를 푸는 함수만 있습니다. A 의 입력을 B 의 입력으로 바꾸는 함수를 짜서 앞에 붙이면 A 도 풀립니다. 이렇게 한 문제를 다른 문제로 바꿔 푸는 일을 환원이라고 합니다.

바꾸는 함수는 다항 시간에 끝나야 합니다. 이 조건을 붙여 「A 가 B 로 다항 시간 환원된다」고 말합니다. 이때 B 는 적어도 A 만큼 어렵습니다. B 를 빨리 푸는 방법이 생기면 A 도 빨리 풀리기 때문입니다.

NP-완전의 정의

결정 문제 X 가 아래 두 조건을 다 채우면 NP-완전이라고 부릅니다.

1. X 가 NP 에 듭니다. 답의 근거를 받으면 다항 시간에 확인할 수 있습니다
2. NP 의 모든 문제가 X 로 다항 시간 환원됩니다

첫째 조건은 따지지 않고 둘째 조건을 채우면 NP-난해라고 부릅니다. NP 만큼 어렵다는 뜻입니다. NP-완전은 NP-난해 가운데 NP 안에도 드는 문제입니다. NP-완전을 「NP 안에서 가장 어려운 문제들」이라고 풀어 말하는 까닭입니다.

표의 마지막 줄은 NP-난해이지만 NP-완전은 아닌 문제를 둘 보입니다. 외판원 순회의 원래 물음은 가장 짧은 경로 자체를 내놓으라고 합니다. 답이 「예·아니요」가 아니라서 NP 에 넣을 수 없습니다. 정지 문제는 어떤 알고리즘으로도 풀 수 없다고 증명된 결정 문제라서 NP 밖에 있습니다.

하나가 풀리면 전부 풀린다

NP-완전 문제 하나를 다항 시간에 푸는 방법이 나왔다고 합시다. NP 의 모든 문제가 그 문제로 환원되므로 NP 의 모든 문제가 다항 시간에 풀립니다. P 와 NP 가 같아진다는 뜻입니다.

연구자 대부분은 P 와 NP 가 다르다고 봅니다. 그 믿음 아래에서는 NP-완전 문제 가운데 어느 것도 다항 시간에 안 풀립니다. 그래서 요구가 NP-완전으로 밝혀지면, 큰 입력에서 정답을 빨리 내는 방법을 찾는 일은 P 대 NP 문제를 푸는 일과 같아집니다.

NP-완전 문제끼리는 서로 환원됩니다. 겉모습은 논리식, 수 목록, 그래프로 제각각입니다. 그래도 어려움은 하나입니다. 이 무리 하나가 NP 전체의 어려움을 빠짐없이 담는다는 뜻에서 「완전」이라는 이름이 붙었습니다.

첫 NP-완전 문제

SAT(Boolean Satisfiability, 불 충족 가능성)는 참·거짓 값을 갖는 변수로 된 논리식을 받습니다. 그리고 식 전체를 참으로 만드는 값 배정이 있는지 묻습니다. 「(a 또는 b) 그리고 (a 아님 또는 c)」가 그런 식입니다. 배정을 근거로 받으면 식에 넣어 보기만 하면 됩니다.

a, b, c = True, False, True     # 받은 배정
(a or b) and (not a or c)       # True

NP 의 모든 문제가 SAT 로 다항 시간 환원된다는 것이 처음으로 증명되었습니다. 이 증명을 쿡-레빈 정리라고 부릅니다. 이로써 SAT 가 NP-완전으로 밝혀진 첫 문제가 되었습니다.

NP-완전임을 보이는 두 단계

SAT 뒤로는 새 문제 X 를 NP 의 모든 문제와 하나하나 견줄 필요가 없습니다. 환원은 이어 붙기 때문입니다. NP 의 모든 문제가 SAT 로 가고 SAT 가 X 로 가면, NP 의 모든 문제가 X 로 갑니다. 그래서 증명은 두 단계로 끝납니다.

1. X 의 답의 근거를 다항 시간에 확인하는 방법을 보입니다
2. 이미 NP-완전으로 밝혀진 문제 하나를 X 로 다항 시간 환원합니다

방향을 거꾸로 잡으면 아무것도 증명하지 못합니다. X 를 SAT 로 환원하면 X 가 SAT 보다 어렵지 않다는 것만 보입니다. 어렵다는 것을 보이려면 이미 어렵다고 알려진 문제에서 X 쪽으로 바꿔야 합니다.

해밀턴 순환에서 외판원 순회로

두 단계를 실물 하나로 봅니다. 출발 문제는 해밀턴 순환이고 도착 문제는 외판원 순회 결정판입니다.

그래프는 점과 그 사이를 잇는 선으로 된 구조입니다. 점을 정점, 선을 간선이라고 부릅니다. 해밀턴 순환 문제는 그래프에서 모든 정점을 한 번씩만 들르고 처음으로 돌아오는 길이 있는지 묻습니다. 이 문제는 NP-완전으로 알려져 있습니다.

외판원 순회 결정판은 도시 사이 거리표를 받습니다. 그리고 모든 도시를 한 번씩 들르고 돌아오는 길이 k 이하인 순회가 있는지 묻습니다. 해밀턴 순환의 그래프를 이 꼴로 바꾸는 함수는 이렇습니다.

def to_tsp(n, edges):
    d = [[2] * n for _ in range(n)]
    for i, j in edges:
        d[i][j] = d[j][i] = 1   # 간선 있음
    return d, n                 # 한도 k = n

정점을 도시로 보고, 간선이 있는 쌍은 거리 1, 없는 쌍은 거리 2 로 둡니다. 그리고 「길이 n 이하인 순회가 있나」를 묻습니다. 순회는 n 번 이동하므로 길이가 n 이하가 되려면 모든 이동이 거리 1, 곧 원래 간선이어야 합니다. 그런 순회가 있다는 것은 해밀턴 순환이 있다는 것과 같습니다.

이 함수는 거리표 n² 칸을 채우고 끝나므로 다항 시간입니다. 이것으로 둘째 단계가 끝났습니다.

첫째 단계도 어렵지 않습니다. 순회를 근거로 받으면 도시를 한 번씩 들렀는지 보고 거리를 더해 k 와 견주면 됩니다. 그래서 외판원 순회 결정판은 NP-완전입니다.

대표 NP-완전 문제

대표 NP-완전 문제는 아래와 같습니다. 모두 결정 문제입니다. 근거를 받으면 확인은 금방 끝납니다.

이 문제들은 SAT 에서 출발해 앞 소절과 같은 환원을 차례로 이어 NP-완전임이 밝혀졌습니다. 흔히 쓰는 환원 사슬은 아래와 같습니다. 화살표는 환원의 방향이고, 화살표 끝의 문제가 적어도 출발 문제만큼 어렵습니다.

flowchart TD
    S["SAT"] --> T["3-SAT"]
    T --> C["클리크"]
    T --> SS["부분집합 합"]
    T --> G["3-색칠"]
    C --> V["정점 덮개"]
    V --> H["해밀턴 순환"]
    H --> TSP["외판원 순회 결정판"]

새 문제를 증명할 때는 이 그림의 어느 문제에서 출발해도 됩니다. 새 문제와 생김새가 가까운 것을 고르면 바꾸는 함수가 짧아집니다.

비슷해 보여도 다항 시간에 풀리는 이웃

조건 하나 차이로 P 와 NP-완전이 갈리는 짝이 많습니다. 아래 표의 왼쪽은 다항 시간에 풀리고 오른쪽은 NP-완전입니다.

2-색칠은 그래프가 이분 그래프인지 묻는 것과 같습니다. 정점들을 두 무리로 나눠, 같은 무리끼리는 간선이 없게 할 수 있는지 묻습니다. 한 정점에서 출발해 이웃마다 반대 색을 칠해 나가면 한 번 훑어서 답이 나옵니다.

이 표는 요구를 조금 바꾸면 반대편으로 넘어갈 수 있다는 뜻이기도 합니다. NP-완전 문제를 만났을 때 먼저 볼 것은 왼쪽 열로 옮길 조건이 요구 안에 숨어 있는지입니다.

백엔드에서 NP-완전을 만났을 때

요구사항은 이 이름을 달고 오지 않습니다. 「회의 시간표를 짜 주세요」 · 「서로 충돌하는 옵션을 피해 설정을 골라 주세요」 · 「서버마다 용량 안에서 작업을 나눠 실어 주세요」처럼 업무 말로 옵니다. 차례로 그래프 색칠, SAT, 빈 패킹 문제와 같은 꼴입니다.

같은 꼴의 이름을 찾으면 쓸 방법이 보입니다. 고르는 방법은 대개 아래 넷입니다.

SAT 풀이기는 NP-완전이라는 성질 덕분에 쓸 수 있는 방법입니다. NP 의 모든 문제가 SAT 로 환원되므로, SAT 를 푸는 프로그램 하나로 이 무리 전체를 다룰 수 있습니다. 최악의 경우, 곧 일이 가장 많아지는 입력에서는 여전히 지수 시간이 걸립니다. 그래도 실무에서 만나는 큰 입력을 자주 풀어 냅니다.

근사 알고리즘은 정답을 포기하는 대신 답이 최적에서 얼마나 멀어질 수 있는지를 보장합니다. 가장 작은 정점 덮개를 찾는 문제에는 「최적의 두 배를 넘지 않는다」를 보장하는 근사 알고리즘이 있습니다. 휴리스틱은 그런 보장 없이 그럴듯한 답을 빠르게 냅니다. 가장 가까운 도시부터 들르는 방식이 외판원 순회의 흔한 휴리스틱입니다.

이 이름이 말해 주지 않는 것

NP-완전은 다항 시간 풀이가 없다는 증명이 아닙니다. P 와 NP 가 다르다는 믿음 아래에서만 그렇게 읽힙니다. 그 믿음은 아직 증명되지 않았습니다.

이 이름은 최악의 경우를 기준으로 붙습니다. 실무 입력은 그보다 훨씬 쉬운 경우가 많습니다. NP-완전 판정은 몇 초 걸리는지 알려 주지 않습니다. 걸리는 시간은 입력을 넣어 따로 잽니다.

부분집합 합과 배낭 문제는 수가 작으면 빨리 풀립니다. 동적 계획법을 쓰면 됩니다. 작은 문제의 답을 표에 적어 두고, 큰 문제를 풀 때 꺼내 쓰는 방법입니다.

부분집합 합이라면 표의 칸 하나에 「앞의 원소 몇 개로 합 w 를 만들 수 있나」를 적습니다. 칸은 원소 수 n 과 목표값 W 를 곱한 만큼 있습니다. 원소 백 개에 목표값이 천이면 칸 십만 개를 채우고 끝납니다.

그런데도 이 문제들이 NP-완전인 까닭은 입력 크기를 재는 방법에 있습니다. 입력 크기는 수의 값이 아니라 수를 적는 데 드는 자릿수로 잽니다.

W 를 적는 자릿수가 하나 늘면 W 는 열 배까지 커질 수 있습니다. 채울 칸도 함께 열 배가 됩니다. 자릿수로 재면 n·W 는 지수 시간인 셈입니다.

수의 값으로 재면 다항, 자릿수로 재면 지수인 시간을 의사 다항 시간이라고 합니다. 의사 다항 시간에 풀리는 NP-완전 문제는 약한 NP-완전이라고 부릅니다. 수가 작을 때만 빨리 풀린다는 뜻입니다.

관련 항목

NP-완전이 속하는 상위 분류

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

NP-완전을 정의하는 데 쓰이는 클래스와 문제 형식

P 클래스 · NP 클래스 · 결정 문제 · 최적화 문제 · 다항 시간 · 지수 시간 · 튜링 기계 · 비결정적 튜링 기계 · 검증기

NP-완전과 포함 관계로 엮이는 복잡도 클래스

NP-난해 · co-NP · co-NP-완전 · NP-중간 · PSPACE-완전 · 강한 NP-완전 · 약한 NP-완전

NP-완전을 증명하는 도구와 정리

환원 · 다항 시간 환원 · 카프 환원 · 쿡-레빈 정리 · P 대 NP 문제 · 카프의 21가지 NP-완전 문제 · 래드너 정리

NP-완전으로 알려진 대표 문제

SAT · 3-SAT · 부분집합 합 문제 · 그래프 색칠 · 최대 클리크 문제 · 정점 덮개 문제 · 독립 집합 문제 · 해밀턴 순환 · 해밀턴 경로 문제 · 외판원 순회 · 배낭 문제 · 빈 패킹 문제 · 분할 문제 · 집합 덮개 문제 · 최장 경로 문제

NP-완전 문제와 겉모습이 닮은 다항 시간 문제

최단 경로 문제 · 오일러 회로 · 2-SAT · 이분 그래프 · 최소 신장 트리

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

완전 탐색 · 백트래킹 · 분기 한정 · 동적 계획법 · SAT 풀이기 · 정수 선형 계획법 · 제약 충족 문제 · 근사 알고리즘 · 휴리스틱 · 메타휴리스틱 · 지역 탐색

NP-완전 판정 밖의 비용을 따지는 분석 방식

최악의 경우 · 평균 경우 분석 · 의사 다항 시간 · 매개변수화 복잡도 · 벤치마크