택배 기사가 하루에 100곳을 돈다. 가장 짧게 도는 순서가 분명히 하나쯤은 있다 — 유한한 경우의 수 안에 답이 들어 있으니까. 그런데 이 최적 경로를 컴퓨터로 정확히 찾으라고 하면, 세상에서 가장 빠른 슈퍼컴퓨터도 우주의 나이보다 오래 걸릴 수 있다. 답이 존재하는데, 찾지를 못한다.
'존재하는 답을 왜 못 찾는가'는 게으름이나 성능의 문제가 아니라, 문제 자체의 성질이다. 이 성질을 정면으로 다루는 학문이 있다.
경우의 수는 왜 이렇게 빨리 폭발할까?
도시가 늘어날 때 경로의 수가 어떻게 커지는지 보자. 도시 몇 곳을 순서대로 방문하는 방법은 순열의 수만큼 있다. 도시가 하나 늘 때마다 후보가 곱절로 불어난다. 몇 곱절이 아니라, 곱하기가 계속 쌓이는 폭발이다. 몇십 개만 넘어가도 후보의 수는 상상하기 어려운 자릿수가 된다.
핵심은 두 종류의 어려움을 나누는 데 있다. 어떤 답을 '검산'하는 것은 쉽다 — 누가 경로 하나를 주면 길이를 더해 확인하면 그만이다. 그런데 '가장 짧은 것'을 처음부터 찾는 것은 후보를 다 훑어야 한다. 검산은 빠른데 탐색은 느린 문제들, 이것이 이야기의 핵심 무대다.
이 현상을 다루는 학문은 무엇인가?
알고리즘론과 그 안의 계산 복잡도 이론이 이 문제를 다룬다. 문제를 '푸는 데 걸리는 시간'이 입력 크기에 따라 어떻게 늘어나는지로 문제를 분류한다. 크기가 커져도 시간이 완만히 느는 문제군을 P, 답을 빠르게 검산할 수 있는 문제군을 NP라 부른다.
여기서 세기의 질문이 나온다. 빠르게 검산되는 모든 문제는 빠르게 풀 수도 있을까(P=NP인가)? 아직 아무도 증명도 반증도 하지 못했다. 이 문제는 오늘날 가장 유명한 미해결 수학·과학 문제 중 하나로 꼽힌다. 답이 '그렇다'로 밝혀지면 공개키 암호를 비롯한 많은 안전장치가 흔들리기에, 정보보안과도 곧장 이어진다.
고등학교에서 배운 무엇과 이어지나?
경우의 수의 폭발은 공통수학1의 경우의 수 단원과 곧장 맞닿는다. 합의 법칙과 곱의 법칙, 순열과 조합이 '후보가 몇 개인지'를 세는 도구다. 도시가 늘 때 경로 수가 순열로 불어나는 것을 직접 계산해 보면, 왜 '전부 확인'이 불가능한지 몸으로 느낄 수 있다.
또 하나는 정보 과목이다. 정렬·탐색 같은 기본 알고리즘을 배우며 '같은 문제도 방법에 따라 걸리는 시간이 크게 다르다'는 것을 경험한다. 그 감각을 문제 전체의 난이도로 확장한 것이 계산 복잡도다.
대학에서는 이걸 어떻게 배우나?
컴퓨터공학과·컴퓨터과학과, 수학과의 일부 전공에서 자료구조·알고리즘·계산이론 과목으로 다룬다. 정확한 최적해를 포기하고 '충분히 좋은 답'을 빠르게 찾는 근사 알고리즘, 무작위를 이용하는 확률 알고리즘 등이 이 어려움에 대응하는 실전 도구로 이어진다. 이론에 얼마나 무게를 두는지는 대학마다 다르므로 개설 과목을 확인하는 편이 좋다.
여기서 뻗어 나갈 탐구 질문 3가지
- 도시 수가 5개, 10개, 15개일 때 경로 후보 수를 직접 계산하면, 증가 속도가 어떤 모양으로 커지는가?
- 정확한 최적해 대신 '꽤 좋은 경로'를 빠르게 찾는 방법(근사)은 어떤 아이디어로 시간을 줄이는가?
- 검산은 쉬운데 탐색은 어려운 문제의 성질을, 암호가 어떻게 '거꾸로' 이용하는가?
한 줄 요약
어떤 문제는 답이 있어도 후보가 폭발해 못 찾는다 — 검산은 쉬운데 탐색은 어려운 이 간극이 컴퓨터과학의 가장 깊은 질문이다.
'풀 수 있다'와 '현실적인 시간에 풀 수 있다'를 구분하는 감각은 공학 탐구의 핵심이다. TimeLevelUp은 이렇게 시작한 궁금증이 탐구로 자라도록 학습 기록을 잇는다.