P 대 NP
풀기 어려운 문제와 채점의 비밀
신문 한구석에 실린 최고 난이도의 스도쿠 빈칸을 연필로 채워 보세요. 모든 숫자가 겹치지 않게 정답을 완성하려면 몇 시간이 걸리거나 꽉 막힙니다.
하지만 누군가 다 채워 둔 스도쿠 답안지를 건네받으면 1분 안에 맞았는지 틀렸는지 바로 검사할 수 있습니다. 답을 채점하기 쉬운 모든 문제는 푸는 것도 빠르게 해낼 수 있을까요?
이야기
Jiří Janíček Pokud hodláte některou z m
CC BY-SA 3.0 · 위키미디어 공용
스도쿠를 푸는 것과, 다 푼 답이 맞는지 확인하는 것 중 어느 쪽이 쉬울까요?
당연히 확인이 쉽습니다. 푸는 데는 한참 걸려도, 확인은 줄과 칸을 훑으면 끝납니다.
그런데 정말 그럴까요? 확인이 빠른 문제는 푸는 것도 빠르지 않을까?
이것이 P 대 NP 문제입니다. P 는 빨리 풀 수 있는 문제들, NP 는 답을 빨리 확인할 수 있는 문제들입니다. 물음은 “P 와 NP 가 같은가?” 입니다.
거의 모든 수학자가 다르다고 믿습니다. 그런데 아무도 증명하지 못했습니다. 1971년에 문제가 제기된 뒤 오십 년이 넘었습니다.
클레이 수학연구소가 백만 달러를 걸었습니다. 일곱 문제 가운데 하나입니다.
만약 P = NP 라면 세상이 뒤집힙니다. 지금 쓰는 암호가 거의 다 깨집니다. 반대로 수많은 어려운 문제가 순식간에 풀립니다.
그리고 놀라운 사실이 있습니다. NP 문제 중 가장 어려운 것들은 서로 통해 있습니다. 하나만 빨리 풀면 전부 빨리 풀립니다.
이 물음이 그토록 무거운 까닭은 수천 개의 문제가 하나로 묶여 있기 때문입니다. 외판원 문제, 스도쿠, 시간표 짜기, 단백질 접힘 — 겉보기에 전혀 다른 이 문제들이 서로 번역됩니다.
그러니 그 가운데 하나만 빨리 푸는 방법이 나오면 전부 빨리 풀립니다. 반대로 하나라도 빨리 풀 수 없다면 전부 그렇습니다. 그래서 이 한 물음에 상금 백만 달러가 걸려 있습니다.
지금 쓰는 암호가 안전한 근거가 「P ≠ NP 일 것」이라는 믿음입니다. 증명된 적이 없습니다.
만약 P = NP 로 밝혀지면 인터넷 암호가 거의 다 무너지고, 동시에 신약 설계·물류·일정 짜기 문제가 순식간에 풀립니다.
계단 넷 — 같은 사실을 네 깊이로
미로 풀기와 답 확인하기를 견준다
복잡하게 엉킨 미로의 입구부터 출구까지 길을 찾는 것은 참 어렵습니다. 갈림길마다 벽에 부딪히며 헤매야 합니다.
하지만 출구까지 빨간 줄이 그어진 정답지를 보면 그 길이 진짜 통과하는 길인지 한눈에 확인할 수 있습니다. 답을 찾는 것과 검사하는 것의 엄청난 차이입니다.
찾기와 확인하기
이 둘이 정말 다른가 — 그것이 P 대 NP 입니다.
스도쿠로 느껴 보기
컴퓨터에서 다항 시간 안에 빠르게 답을 찾을 수 있는 문제들의 모임을 P라고 부릅니다. 반면, 답을 찾는 것은 어려워 보여도 정답 후보가 주어졌을 때 맞는지 틀렸는지를 빠르게 검산할 수 있는 문제들의 모임을 NP라고 합니다.
스도쿠나 외판원의 최단 경로 문제는 모두 NP에 속합니다. 검산이 쉬우면 푸는 것도 항상 쉬운 알고리즘이 존재할까요? 이것이 100만 달러가 걸린 밀레니엄 난제입니다.
얼마나 차이 나나
n² 은 언제나 눈 깜짝할 사이입니다.
환원의 뜻
스티븐 쿡과 레오니드 레빈은 NP-완전(NP-Complete)이라는 놀라운 개념을 정립했습니다. 불리언 충족 가능성 문제(SAT)와 같은 NP-완전 문제는 모든 NP 문제들이 다항 시간 안에 환원(Polynomial-time Reduction)될 수 있는 가장 어려운 핵심 핵입니다.
만약 단 하나의 NP-완전 문제라도 다항 시간 알고리즘(P)으로 풀 수 있다면, 기적처럼 모든 NP 문제들이 한꺼번에 P가 되어 가 증명됩니다. 대부분의 컴퓨터 과학자들은 일 것으로 추측합니다.
하나를 풀면 다 풀립니다
하나만 빠르게 풀면 3000 가지가 다 풀립니다 — 쿡–레빈 정리.
밀레니엄 문제
P 대 NP 문제는 계산 복잡도 이론(Computational Complexity Theory)의 알파이자 오메가입니다. 만약 라면 현대 암호 체계(RSA, ECC)는 즉시 붕괴하지만, 단백질 접힘 예측, 수학적 증명 자동화, 전 지구적 물류 최적화가 순식간에 실시간으로 해결됩니다.
인간의 창의적 직관과 탐색의 한계를 계산 기계의 언어로 엄밀하게 묻는 인류 지성사 최고의 근본 질문 중 하나입니다.
상금이 걸려 있습니다
대부분의 학자는 P ≠ NP 일 것이라 봅니다. 그러나 아무도 증명하지 못했습니다.
풀어 보기
계산 복잡도와 P 대 NP. 다음 물음에 답하시오.
(1) 크기가 인 배열의 숫자들을 크기순으로 정렬하는 문제가 클래스 P에 속하는 까닭을 시간 복잡도를 들어 설명하시오.
(2) NP 문제의 정의를 '해의 검증 시간' 관점에서 한 문장으로 서술하시오.
(3) 외판원 문제(TSP)와 같은 NP-완전 문제 중 하나가 다항 시간 에 풀릴 경우, P와 NP의 집합 관계가 어떻게 되는지 쓰시오.
(1) 퀵정렬이나 병합정렬 등으로 다항 시간에 해결되기 때문입니다. (3) 가 됩니다.
답과 풀이 보기
(1) 병합정렬·퀵정렬 등으로 에 끝나기 때문입니다.
은 보다 작으므로 다항 시간이고, 그런 문제들의 모임이 클래스 P 입니다.
⭐ 자료가 100 배 늘어도 시간은 약 200 배밖에 안 늘어납니다. 감당할 수 있는 증가입니다.
(2) 답을 하나 주었을 때 그것이 맞는지 다항 시간 안에 확인할 수 있는 문제입니다.
⭐ 푸는 것과 맞는지 보는 것은 다릅니다. 스도쿠를 푸는 것은 어렵지만, 다 채운 답이 맞는지 보는 것은 한눈에 됩니다.
P 는 NP 안에 들어 있습니다 (풀 수 있으면 확인도 할 수 있으니까요).
(3) 가 됩니다.
NP-완전 문제는 NP 안의 모든 문제를 다항 시간에 옮겨 담을 수 있는 문제입니다.
그러니 그런 문제가 하나라도 다항 시간에 풀리면, NP 의 모든 문제가 그 방법을 빌려 다항 시간에 풀립니다.
⇨ 이고 이미 이므로 .
이것은 백만 달러가 걸린 일곱 문제 가운데 하나입니다 (클레이 연구소).
만약 라면 — 인터넷 암호가 모두 풀리고, 신약 설계와 물류가 단숨에 풀리고, 수학의 증명조차 기계가 찾아냅니다.
대부분의 학자는 라고 믿습니다. 그런데 50 년 동안 아무도 증명하지 못했습니다. '답을 알아보기는 쉬운데 찾기는 어렵다'는 당연해 보이는 말이 증명되지 않고 있습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「어렵다」를 수학으로 다루는 분야입니다.
- NP 완전 — 스도쿠·외판원·배낭 문제가 모두 여기 속합니다
- 암호 — 「푸는 것이 어렵다」는 믿음 위에 서 있습니다
- 쿡·레빈 정리 — 「하나가 풀리면 전부 풀린다」를 보인 결과입니다
이어지는 장
방문할 도시가 조금만 늘어도 컴퓨터가 가장 짧은 길을 찾지 못해 멈칫거리던 난제가 바로 이 물음입니다 — 제52장 의 외판원 문제가 현대 수학과 컴퓨터 과학 최대의 벽으로 닿습니다.
영감을 받은 곳
스티븐 쿡(Stephen Cook)이 1971년 계산 복잡도 학술대회(STOC)에 발표한 논문 「The Complexity of Theorem-Proving Procedures」에서 공식 제기했습니다.