NP-난해

NP-난해는 어떤 문제가 빠르고 정확하게 풀리기를 기대하기 어렵다고 알려 줍니다. 이 이름이 붙은 문제는 알려진 어떤 방법으로도 큰 입력의 정답을 빨리 못 구합니다. 배송 경로 짜기와 시간표 배정이 대표입니다. 이 이름을 확인한 개발자는 정답 대신 최적에 가까운 답을 찾는 쪽으로 방향을 바꿉니다.

상세

시험지에 문제가 열 개 있다고 합시다. 그중 한 문제만 풀 줄 알면 나머지 아홉도 그 문제로 바꿔 풀 수 있습니다. 그렇다면 그 한 문제는 적어도 다른 아홉만큼은 어렵습니다.

NP-난해는 이 생각을 문제의 모임에 옮긴 이름입니다. 시험지 대신 「답을 빨리 확인할 수 있는 문제」의 모임 NP(Nondeterministic Polynomial time)를 놓습니다. 이름의 뜻은 아래 「P 와 NP」 절에서 풉니다. NP 의 모든 문제를 바꿔 풀게 해 주는 문제가 NP-난해 문제입니다.

이 절은 결정 문제와 다항 시간으로 두 문제 모임 P(Polynomial time)와 NP 를 먼저 세웁니다. 이어서 문제를 바꿔 푸는 환원을 들여옵니다. 그다음 NP-난해를 정의하고 이웃 이름 NP-완전과 가릅니다. 끝으로 백엔드에서 이 이름을 만났을 때 고르는 길을 봅니다.

결정 문제와 최적화 문제

결정 문제는 답이 「예」나 「아니요」인 문제입니다. 「이 목록에 7 이 있나」가 결정 문제입니다. 답의 꼴을 하나로 맞춰 두면 서로 다른 문제끼리 어려움을 견주기 쉬워집니다.

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

다항 시간과 지수 시간

다항 시간은 입력 크기 n 에 대해 n², n³ 처럼 n 을 정해진 횟수만큼 곱한 값을 넘지 않는 시간입니다. 입력이 두 배가 되어도 시간은 정해진 배수로만 늡니다. n² 이면 네 배입니다.

반대편에는 지수 시간이 있습니다. 2ⁿ 처럼 n 이 하나 늘 때마다 시간이 두 배가 됩니다. 후보 하나를 확인하는 데 1마이크로초가 든다고 합시다. 후보 2ⁿ 개를 전부 확인하면 이렇게 됩니다.

2 ** 20  # 1,048,576 → 약 1초
2 ** 40  # 약 1조 → 약 13일
2 ** 60  # 약 115경 → 약 3만 6천 년

입력이 스무 개 늘 때마다 시간이 백만 배쯤 늡니다. 그래서 다항 시간은 컴퓨터로 감당할 수 있는 문제의 경계로 흔히 쓰입니다. 지수 시간은 입력이 조금만 커져도 감당 못 하는 쪽입니다.

P 와 NP

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

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

이름 NP 는 Nondeterministic Polynomial time, 곧 「비결정적 다항 시간」을 줄인 말입니다. 「비결정적」은 갈림길마다 맞는 쪽을 알아서 골라 주는 가상의 기계를 가리킵니다. 그런 기계는 답을 바로 짐작해 놓고 다항 시간에 확인만 하면 됩니다. 그래서 이 이름과 「확인이 빠르다」는 정의는 같은 모임을 가리킵니다.

부분집합 합 문제가 NP 의 대표입니다. 수 목록 [3, 34, 4, 12, 5, 2] 에서 몇 개를 골라 합을 9 로 만들 수 있는지 묻습니다. 누가 「4 와 5」라는 근거를 주면 더해 보기만 하면 됩니다.

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

P 의 문제는 모두 NP 에도 듭니다. 받은 근거를 쓰지 않고 다항 시간에 직접 풀어 답을 맞춰 보면, 그것으로 확인이 끝나기 때문입니다.

거꾸로 NP 의 문제가 모두 P 에 드는지는 아무도 증명하지 못했습니다. P 와 NP 가 같은지 묻는 이 물음이 P 대 NP 문제입니다.

문제를 바꿔 푸는 환원

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

def solve_a(a_input):
    b_input = convert(a_input)  # 다항 시간
    return solve_b(b_input)     # = A 의 답

convert 는 다항 시간에 끝나야 합니다. 바꾸는 데 지수 시간이 들면 B 가 아무리 빨라도 A 는 느립니다. 이 조건을 붙여 「A 가 B 로 다항 시간 환원된다」고 말합니다.

A 가 B 로 환원되면 B 는 적어도 A 만큼 어렵습니다. B 를 빨리 푸는 방법이 생기면 A 도 빨리 풀리기 때문입니다. 두 문제의 풀이를 몰라도 어느 쪽이 더 어려운지는 말할 수 있게 됩니다.

NP-난해의 정의

NP 의 모든 문제가 문제 X 로 다항 시간 환원되면 X 를 NP-난해라고 부릅니다. 첫머리의 시험지로 말하면 X 는 NP 의 모든 문제를 대신 풀어 주는 문제입니다.

그래서 NP-난해 문제 하나를 다항 시간에 푸는 방법이 나오면 NP 의 모든 문제가 다항 시간에 풀립니다. P 와 NP 가 같아진다는 뜻입니다. 연구자 대부분은 둘이 다르다고 봅니다. 그 믿음 아래에서 NP-난해 문제는 다항 시간에 안 풀립니다.

이 판정은 헛수고를 막는 데 쓰입니다. 요구가 NP-난해로 밝혀지면, 큰 입력에서 빠른 정답을 내는 방법을 찾는 일은 P 대 NP 문제를 푸는 일과 같아집니다. 수십 년 동안 아무도 못 푼 문제입니다. 그 시간에 근사나 입력 제한 쪽으로 설계를 돌립니다.

한 번의 환원으로 증명하기

NP 의 문제를 하나하나 새 문제로 환원해 보일 수는 없습니다. NP 에 든 문제는 끝이 없기 때문입니다. 실제 증명은 이미 어렵다고 밝혀진 문제 하나에서 새 문제로 한 번만 환원합니다. 환원을 시작하는 그 문제를 출발점이라고 하겠습니다.

첫 출발점은 SAT(Boolean Satisfiability)입니다. 참·거짓 값을 갖는 변수로 된 논리식이 있을 때, 식 전체를 참으로 만드는 값 배정이 있는지 묻는 결정 문제입니다. 「(x 또는 y) 그리고 (x 가 아님)」이라면 x 를 거짓, y 를 참으로 두면 식이 참이 됩니다. 그래서 이 식에 대한 답은 「예」입니다.

NP 의 모든 문제가 SAT 로 환원된다는 것이 처음으로 증명되었습니다. 이 증명을 쿡-레빈 정리라고 부릅니다. 그 덕에 SAT 는 다른 문제의 출발점이 될 수 있었습니다.

그 뒤로 새 문제는 SAT 하나만 자기에게 환원해 보이면 됩니다. 환원은 이어 붙기 때문입니다. NP 의 모든 문제가 SAT 로 가고 SAT 가 새 문제로 가면, NP 의 모든 문제가 새 문제로 갑니다.

flowchart TD
    A["NP 의 모든 문제"] -->|"환원 · 쿡-레빈 정리"| B["SAT"]
    B -->|"환원 · 새로 보일 것"| C["새 문제"]
    A -.->|"이어 붙어 저절로 성립"| C

출발점이 꼭 SAT 일 필요는 없습니다. 이미 NP-난해로 밝혀진 문제라면 무엇에서 출발해도 같습니다. 부분집합 합 문제나 외판원 순회가 흔한 출발점입니다.

외판원 순회는 모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 경로를 묻는 문제입니다. 배송 기사가 여러 곳을 도는 순서 짜기가 바로 이 꼴입니다.

방향을 거꾸로 잡으면 아무것도 증명하지 못합니다. 새 문제를 SAT 로 환원하면 새 문제가 SAT 보다 어렵지 않다는 것만 보입니다. 어렵다는 것을 보이려면 어려운 문제에서 새 문제 쪽으로 화살표를 그어야 합니다.

NP-난해와 NP-완전

NP-완전은 NP-난해이면서 NP 안에도 드는 문제입니다. NP 안에서 가장 어려운 문제들이라는 뜻입니다. SAT, 부분집합 합 문제, 외판원 순회의 결정판이 여기 듭니다.

이름에 NP 가 들어 있어 NP-난해를 NP 의 일부로 읽기 쉽습니다. NP-난해는 「NP 만큼 어렵다」는 뜻이지 「NP 에 든다」는 뜻이 아닙니다. 그래서 NP-난해이지만 NP-완전이 아닌 문제가 있습니다. 갈래는 둘입니다.

첫째는 답이 「예·아니요」가 아닌 최적화 문제입니다. 외판원 순회의 원래 물음은 「가장 짧은 경로를 구하라」입니다. 답이 경로라서 NP 에 넣을 수 없습니다. 그래도 가장 짧은 경로를 구하면 결정판에 바로 답할 수 있으므로 적어도 결정판만큼 어렵습니다.

둘째는 NP 보다 훨씬 어려운 결정 문제입니다. 정지 문제는 프로그램이 언젠가 멈추는지 묻습니다. 어떤 알고리즘으로도 풀 수 없다고 증명된 문제입니다. 그래도 NP 의 모든 문제가 이리로 환원되므로 NP-난해에 듭니다.

세 이름은 두 조건으로 갈립니다. NP 에 드는지, 그리고 NP 의 모든 문제가 그리로 환원되는지입니다.

백엔드에서 만나는 NP-난해 문제

요구사항은 이 이름을 달고 오지 않습니다. 「배송 순서 짜 주세요」처럼 업무 말로 옵니다. 아래 표는 흔한 요구와, 그 요구와 같은 꼴인 문제를 짝지었습니다.

요구를 오른쪽 이름으로 바꿔 부르면 길이 열립니다. 그 이름 아래 이미 연구된 풀이와 근사 방법이 쌓여 있기 때문입니다.

NP-난해로 밝혀진 뒤에 고르는 길

NP-난해라는 판정은 「큰 입력」 · 「빠름」 · 「정답」 셋을 한꺼번에 얻기는 어렵다는 뜻입니다. 하나를 내려놓아야 합니다. 무엇을 내려놓느냐에 따라 길이 갈립니다. 표로 먼저 보고 아래에서 하나씩 풉니다.

입력이 작으면 완전 탐색으로 후보를 전부 확인합니다. 원소가 스무 개 남짓이면 2ⁿ 도 백만 번 정도라 금방 끝납니다.

분기 한정은 더 볼 필요가 없는 후보 묶음을 중간에 잘라 냅니다. 같은 정답을 더 빨리 찾지만 최악의 경우에는 여전히 지수 시간이 듭니다.

근사 알고리즘은 정답을 포기하는 대신 「최적의 두 배를 넘지 않는다」 같은 보장을 줍니다. 답이 최적에서 얼마나 멀어질 수 있는지를 미리 알고 쓸 수 있습니다.

외판원 순회에도 이런 보장이 붙는 경우가 있습니다. 두 지점 사이를 바로 가는 길이 다른 곳을 거쳐 가는 길보다 길지 않다는 조건을 삼각 부등식이라고 합니다. 거리가 이 조건을 지키면 두 배 보장을 주는 방법이 알려져 있습니다.

휴리스틱은 보장 없이 그럴듯한 답을 빠르게 냅니다. 최적에서 얼마나 먼지는 알 수 없습니다.

탐욕 알고리즘은 휴리스틱의 흔한 예입니다. 매번 그때 가장 좋아 보이는 쪽을 고르고 되돌아보지 않습니다. 배송이라면 지금 위치에서 가장 가까운 곳부터 들릅니다.

지역 탐색은 답 하나를 먼저 만들어 놓고 조금씩 고쳐 나갑니다. 방문 순서에서 두 곳을 맞바꿔 보고 경로가 짧아지면 그 순서를 받아들이는 식입니다. 더 고칠 데가 없으면 멈춥니다.

입력을 좁히면 쉬운 문제가 되기도 합니다. 앞 표의 회의 배정은 참석자가 겹치는 회의끼리 다른 시간대에 넣는 일이었습니다. 회의를 점, 겹침을 선으로 놓고 선으로 이어진 점끼리 다른 색을 칠하는 그래프 색칠입니다. 색 하나가 시간대 하나입니다.

같은 문제를 좁혀 봅시다. 회의마다 시작과 끝 시각이 이미 정해져 있다고 합시다. 이제 시각이 겹치는 회의끼리 다른 회의실에 넣습니다. 겹침의 기준이 참석자에서 시각으로 바뀌고 색 하나가 회의실 하나가 되었을 뿐, 여전히 색칠 문제입니다.

이렇게 좁히면 필요한 회의실 수는 회의를 시작 시각 순으로 한 번 훑어 구합니다. 아무 겹침이나 받던 그래프 색칠과 달리 다항 시간에 풀립니다.

이 이름이 말해 주지 않는 것

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

또 이 이름은 최악의 경우, 곧 일이 가장 많아지는 입력을 기준으로 붙습니다. 실무에서 만나는 입력은 금방 풀리는 경우가 많습니다. NP-완전인 SAT 도 전용 SAT 풀이기가 큰 실무 입력을 자주 풀어 냅니다.

그래서 NP-난해 판정은 몇 초 걸리는지 알려 주지 않습니다. 풀이의 방향을 고르는 데 쓰고, 걸리는 시간은 입력을 넣어 따로 잽니다.

관련 항목

NP-난해가 속하는 상위 분류

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

NP-난해를 정의하는 데 쓰이는 클래스와 문제 형식

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

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

NP-완전 · co-NP · PSPACE · EXPTIME · 강한 NP-난해 · APX

NP-난해를 증명하는 도구와 정리

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

NP-난해로 알려진 대표 문제

SAT · 3-SAT · 부분집합 합 문제 · 외판원 순회 · 배낭 문제 · 빈 패킹 문제 · 그래프 색칠 · 해밀턴 경로 문제 · 정점 덮개 문제 · 최대 클리크 문제 · 차량 경로 문제 · 작업장 스케줄링 · 정지 문제

NP-난해 문제 앞에서 고르는 풀이 방법

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

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

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