🟣 어떤 문제는 빠른 답이 없다
지금까지의 알고리즘은 전부 다항 시간에 돌았다. 정렬은 O(n log n), 최단 경로는 O(E log V), DP는 O(mn)이나 O(n³)이었다. 입력이 커져도 감당할 만한 속도다. 그런데 겉보기엔 비슷하게 생긴 문제인데 아무도 다항 시간 알고리즘을 찾지 못한 것들이 있다.
외판원 문제(TSP)가 대표다. 도시 여러 개를 모두 한 번씩 돌아 출발점으로 오는 가장 짧은 경로를 찾는 문제다. 앞 장의 최단 경로와 닮았지만 난이도가 전혀 다르다. 가능한 경로가 도시 수의 팩토리얼로 늘어나고, 이걸 다항 시간에 줄이는 방법을 반세기 넘게 아무도 찾지 못했다. 이 장은 왜 어떤 문제는 어렵고, 그런 문제를 실무에서 마주치면 어떻게 하는가를 다룬다.
🟣 P와 NP: 푸는 것과 확인하는 것
문제의 난이도를 가르는 두 부류가 있다. P는 다항 시간에 답을 구할 수 있는 문제들이다. 지금까지 다룬 정렬, 최단 경로, MST가 전부 P에 속한다.
NP는 조금 다르게 정의된다. 누가 답을 하나 제시하면 그게 맞는지 다항 시간에 확인할 수 있는 문제들이다. 여기서 핵심은 "확인"과 "구하기"의 간극이다. TSP에서 경로 하나를 주면 길이를 재서 기준보다 짧은지 금방 확인할 수 있다. 확인은 쉽다. 그런데 그런 경로를 처음부터 찾아내는 건 어렵다.
모든 P 문제는 NP에 속한다. 다항 시간에 풀 수 있으면 확인도 당연히 다항 시간이기 때문이다. 문제는 그 반대다. 확인이 쉬운 모든 문제는 푸는 것도 쉬운가. 이것이 P = NP인가라는 컴퓨터 과학 최대의 미해결 문제다. 대부분의 연구자는 P ≠ NP, 즉 확인은 쉬워도 푸는 게 근본적으로 어려운 문제가 존재한다고 믿지만 아직 증명되지 않았다.
🟣 NP-완전: 가장 어려운 문제들과 환원
NP 안에서도 가장 어려운 문제들이 있다. 이들을 NP-완전이라 부른다. 정의의 핵심은 환원(reduction)이다. 문제 A를 문제 B로 바꿔 푸는 변환이 다항 시간에 되면, "A는 B로 환원된다"고 한다. 이때 B를 풀 수 있으면 A도 풀 수 있으니 B는 A만큼은 어렵다.
NP-완전 문제는 NP의 모든 문제가 그것으로 환원되는 문제다. 즉 NP에서 가장 어려운 축에 속한다. 여기서 놀라운 결론이 나온다. NP-완전 문제 단 하나라도 다항 시간에 풀리면 NP의 모든 문제가 다항 시간에 풀린다. 환원을 타고 전부 내려오기 때문이다. 그러면 P = NP가 된다. 반대로 하나라도 다항 시간에 못 풀림이 증명되면 P ≠ NP다.
역사적으로 처음 NP-완전임이 증명된 문제가 불리언 만족성 문제(SAT)다. 논리식을 참으로 만드는 변수 할당이 있는지 묻는 문제다. 이후 3-SAT, 정점 커버, 클리크, 부분집합 합, 그래프 색칠, 앞서 본 TSP까지 수천 개의 문제가 서로 환원 가능한 NP-완전 무리로 묶였다. 겉모습은 제각각인데 속을 열어 보면 전부 같은 난이도의 한 문제라는 사실이 이 이론의 힘이다. 새 문제가 이 무리로 환원됨을 보이면, 그 문제도 다항 알고리즘을 기대하지 말라는 신호다.
🟣 어려운 문제를 실무에서 만나면
P = NP를 증명하러 갈 게 아니라면, NP-완전 문제를 마주쳤을 때의 실전 대응이 더 중요하다. 정확한 다항 해를 포기하는 대신 세 갈래 타협이 있다.
첫째는 근사 알고리즘이다. 최적은 못 구해도, 최적에 일정 비율 이내로 가까운 답을 다항 시간에 보장한다. 정점 커버 문제가 좋은 예다. 아직 덮이지 않은 간선을 하나 골라 그 양 끝 정점을 모두 답에 넣기를 반복하면, 최적의 두 배를 넘지 않는 커버를 다항 시간에 얻는다. "최적의 2배 이내"라는 보장이 붙은 2-근사다. 근사 알고리즘의 값어치는 이 보장된 품질에 있다.
둘째는 휴리스틱이다. 품질 보장은 없지만 현실 입력에서 대체로 좋은 답을 빠르게 낸다. TSP를 가까운 도시부터 잇는 최근접 이웃 방식이나 유전 알고리즘으로 푸는 것이 여기 속한다. 이론적 보장이 없어도 실무에서는 "충분히 좋으면 된다"가 통하는 경우가 많다.
셋째는 문제 자체를 좁히기다. 일반 그래프에서는 NP-완전이어도, 트리나 평면 그래프처럼 입력에 제약을 걸면 다항 시간에 풀리는 특수 경우가 흔하다. 실무의 입력이 그 특수 형태에 들어맞는지 살피는 것이 먼저다.
🟣 백트래킹: 지수를 정면으로 풀되 영리하게
근사도 휴리스틱도 못 쓰고 정확한 답이 꼭 필요할 때가 있다. 입력이 작다면 지수 시간을 감수하고 정확히 푸는 선택도 유효하다. 이때 무작정 모든 경우를 나열하는 대신 쓰는 기법이 백트래킹이다.
백트래킹은 후보를 한 단계씩 조립해 가다가, 지금까지의 선택이 절대 답이 될 수 없다고 판명되면 그 가지를 통째로 버리고 되돌아온다(가지치기, pruning). N-Queen 문제에서 퀸을 한 줄씩 놓다가 이미 놓인 퀸과 공격 관계가 생기면, 그 아래 경우를 전부 시도하지 않고 즉시 물러난다. 이론상 최악은 여전히 지수지만, 가지치기가 탐색 공간을 실질적으로 크게 줄여 작은 입력에서는 충분히 빠르다.
가지치기가 얼마나 촘촘한지가 백트래킹의 실용성을 좌우한다. 불가능을 얼마나 일찍 알아채느냐가 곧 속도다. 이 감각은 스도쿠 풀이기나 제약 만족 문제에서 그대로 쓰인다.
🟣 정리
- 겉보기에 비슷해도 어떤 문제는 다항 시간에 풀리고(P) 어떤 문제는 아무도 다항 해를 못 찾았다. TSP가 후자의 대표다.
- NP는 답을 주면 다항 시간에 확인할 수 있는 문제들이다. 확인이 쉬운 모든 문제가 푸는 것도 쉬운가라는
P = NP물음은 아직 미해결이다. - NP-완전 문제는 NP에서 가장 어렵고 서로 환원된다. 하나라도 다항 시간에 풀리면 전부 풀린다. 새 문제가 이 무리로 환원되면 다항 해를 기대하지 말라는 신호다.
- 실무 대응은 세 갈래다. 품질을 보장하는 근사, 보장은 없지만 빠른 휴리스틱, 입력을 특수 형태로 좁히기.
- 정확한 답이 꼭 필요하고 입력이 작으면 백트래킹으로 지수를 정면으로 푼다. 불가능을 일찍 알아채는 가지치기가 속도를 만든다.
NP-완전성은 추상적으로 보이지만 실무 판단으로 곧장 이어진다. 어떤 기능 요구사항이 사실 배낭이나 스케줄링 같은 NP-완전 문제임을 알아채면, "정확히 최적으로 풀겠다"는 약속 대신 "근사로 충분히 좋게 풀겠다"는 현실적 설계로 방향을 튼다. 풀 수 없음을 아는 것이 잘못된 완벽주의를 막아 준다는 점이 이 마지막 장의 가장 실용적인 교훈이었다. 여기까지가 알고리즘을 하나의 축으로 엮은 기록이다. 빠르기를 재는 자에서 시작해, 문제 구조에 맞는 설계 기법을 지나, 풀 수 없는 문제 앞에서 타협하는 법까지 왔다.