알고리즘과 자료구조 4강. 빠르다는 말의 뜻
100만 달러가 걸린 미해결 문제의 정체는 이렇습니다. 답을 채점하기는 쉬운데 답을 찾기는 어려운 문제가, 정말로 어려운 게 맞습니까.
풀고 시작
초 단위로 말하면 틀립니다
"이 알고리즘은 0.3초 걸립니다"라는 말은 정보량이 거의 없습니다. 어느 기계에서, 어떤 언어로, 몇 개의 데이터로 쟀는지에 따라 통째로 달라지니까요. 그래서 계산 복잡도는 시간을 재는 대신 입력 크기 n이 커질 때 연산 횟수가 어떤 속도로 늘어나는가를 봅니다. 이때 쓰는 표기가 점근 표기법, 흔히 말하는 빅오입니다. 3n² + 500n + 9000을 그냥 O(n²)이라고 적죠. 계수와 낮은 차수 항을 버리는 이유는 n이 충분히 커지면 최고 차수 항이 결과를 지배하기 때문입니다. 다만 이 관행에는 정직한 단서가 붙습니다. 버려진 상수가 실제로는 아주 클 수 있고, 데이터가 작을 때는 O(n²) 알고리즘이 O(n log n) 알고리즘보다 빠른 일이 흔합니다. 표준 라이브러리의 정렬이 작은 구간에서 삽입 정렬로 갈아타는 것이 그 증거죠. 점근 표기법은 규모가 커질 때의 운명을 알려 주는 도구이지, 지금 이 입력에서 무엇이 빠른지 답해 주는 도구가 아닙니다.
다항과 지수 사이의 절벽
증가 속도의 차이는 어느 지점에서 정도의 문제가 아니라 종류의 문제가 됩니다. n²과 2ⁿ을 나란히 놓아 보죠. n이 10일 때는 100 대 1024로 엇비슷합니다. n이 50이면 2500 대 약 1000조가 되고, n이 100이면 1만 대 2¹⁰⁰인데 2¹⁰⁰은 우주의 나이를 나노초로 센 것보다도 큽니다. 기계를 백만 배 빠르게 만들어도 지수 알고리즘이 다룰 수 있는 n은 스무 남짓 늘어날 뿐입니다. 그래서 이론 컴퓨터과학은 다항 시간에 풀리면 다루기 쉬운 문제, 그렇지 않으면 다루기 어려운 문제라는 선을 긋습니다. 코브햄과 에드먼즈의 이름이 붙은 이 기준에도 반론은 있습니다. n¹⁰⁰도 형식상 다항이지만 실제로는 쓸모가 없고, 반대로 지수 알고리즘이라도 현실의 입력에서는 잘 도는 경우가 있으니까요. 그럼에도 이 선이 살아남은 이유는 그것이 기계 종류나 프로그래밍 언어를 바꿔도 흔들리지 않는 견고한 경계이기 때문입니다.
채점은 쉬운데 풀기는 어렵다
이제 본론입니다. P는 다항 시간 안에 답을 구할 수 있는 문제들의 모음입니다. NP는 답을 구하는 난이도가 아니라 검증의 난이도로 정의됩니다. 어떤 답이 맞다고 주장하는 근거를 누가 건네주면 그것이 맞는지 다항 시간에 확인할 수 있는 문제들이죠. 스도쿠를 떠올리면 감이 옵니다. 다 채워진 판을 받아 규칙 위반이 있는지 확인하는 일은 금방이지만, 빈칸에서 시작해 답을 찾는 일은 전혀 다른 이야기입니다. 큰 수가 두 소수의 곱인지도, 답인 소수 두 개를 받으면 곱해 보면 그만이지만 직접 찾는 것은 어렵습니다. 여기서 P가 NP에 포함된다는 사실은 자명합니다. 직접 풀 수 있으면 검증도 당연히 되니까요. 그래서 진짜 질문은 하나 남습니다. 검증만 쉬운 문제 중에 사실은 풀이도 쉬운데 우리가 방법을 못 찾은 것뿐인 문제가 있는가. 이것이 P 대 NP 문제입니다.
하나가 무너지면 전부 무너진다
이 질문이 왜 그토록 무거운지는 환원(reduction)을 알아야 이해됩니다. 문제 A의 입력을 다항 시간에 문제 B의 입력으로 바꿔 풀 수 있다면, B를 푸는 방법은 곧 A를 푸는 방법입니다. 이때 B는 최소한 A만큼 어렵죠. 1971년 스티븐 쿡은 논리식의 만족 가능성 문제(SAT)로 NP의 모든 문제를 환원할 수 있음을 보였고, 레오니트 레빈이 비슷한 시기에 독립적으로 같은 결론에 이르렀습니다. 이런 문제를 NP-완전이라 부릅니다. 이듬해 리처드 카프는 스물한 개의 익숙한 문제가 모두 NP-완전임을 보였고, 이후 수천 개가 이 목록에 합류했습니다. 결과는 극적입니다. NP-완전 문제 단 하나라도 다항 시간 알고리즘이 발견되면 그 순간 NP 전체가 P가 됩니다. 반세기 넘게 수많은 사람이 매달렸는데 그런 알고리즘이 하나도 안 나왔다는 사실이 P와 NP가 다르다는 심증의 근거이지만, 심증은 증명이 아닙니다. 클레이 수학연구소는 2000년 이 문제를 밀레니엄 문제로 지정하며 100만 달러를 걸었습니다. 판돈에 관해서는 정확히 말할 필요가 있습니다. P가 NP와 같고 실제로 쓸 만한 알고리즘이 구성된다면 신약 설계나 물류 최적화가 뒤집히는 한편 현대 공개키 암호의 상당 부분이 위태로워집니다. 다만 오늘날 널리 쓰이는 소인수분해 기반 암호에 대해 말하자면, 소인수분해는 NP에 속하지만 NP-완전으로 알려져 있지는 않습니다.
못 풀면 어떻게 삽니까
현실의 물류 회사는 P 대 NP가 풀릴 때까지 배송을 멈추지 않습니다. 어려운 문제와 함께 사는 방법이 있기 때문입니다. 첫째는 근사 알고리즘입니다. 최적해를 포기하는 대신 최적해의 몇 배 이내라는 보장을 수학적으로 증명해 붙입니다. 도시 간 거리가 삼각 부등식을 만족하는 외판원 문제에서 최적 경로의 1.5배 이내를 보장하는 크리스토피데스 알고리즘이 고전적인 예입니다. 둘째는 휴리스틱입니다. 보장은 없지만 실제 데이터에서 잘 통하는 경험적 전략이죠. 셋째는 문제의 특수 구조를 활용하는 것입니다. 현실의 입력은 무작위 최악의 경우가 아니라 규칙성을 품고 있어서, 오늘날의 SAT 솔버는 변수가 수십만 개인 산업 문제를 일상적으로 풀어냅니다. 최악의 경우 지수 시간이라는 사실은 그대로 참인데도 말이죠. 어렵다는 판정은 모든 입력에 대한 최악의 진술이지, 내 앞의 입력에 대한 사형 선고가 아닙니다. 다음 강에서는 아무리 오래 기다려도 답이 나오지 않는, 훨씬 근본적인 벽을 만납니다.
인출 문제
생각해볼 질문 (정답 없음)
- 만약 P와 NP가 같다는 것이 증명되었는데 그 증명이 실제 알고리즘을 하나도 알려 주지 않는 방식이라면, 세상은 무엇이 달라질까요.
이전: 알고리즘과 자료구조 3강 · 다음: 알고리즘과 자료구조 5강