어떻게 안 풀리는 문제도 있을까

경우의 수가 폭발한다

한 사람이 여러 도시를 모두 한 번씩 돌면서 가장 짧은 길을 찾고 싶다고 하자.
도시가 셋이면 돌아보는 순서가 몇 가지 안 된다. 그런데 도시를 하나씩 늘리면 따져 볼 순서의 수가 눈 깜짝할 새 어마어마해져요.
아래 단추로 도시를 늘려 보자.

도시를 늘리면 돌아보는 순서의 수가 폭발한다. (도시 +1 → 경우의 수 곱하기)

도시가 늘 때마다 순서의 수가 곱하기로 불어난다. 빅오에서 본 '폭발하는 자람'이 바로 이것이다.
도시가 열 몇 개만 돼도 순서가 너무 많아서, 하나하나 다 따져 보는 길은 금방 막혀요.

풀기는 어렵지만 확인은 쉽다

그런데 재미있는 점이 있다. 답을 찾기는 어려워도 누가 답을 가져오면 그것이 맞는지 확인하는 일은 금방이다.
스도쿠를 떠올려 보자. 빈칸을 다 채우기는 머리가 아프지만, 다 채워진 판이 규칙에 맞는지 검사하는 일은 눈으로 죽 훑으면 끝나요.

답 후보를 누르면 확인은 금방 끝난다. (찾기는 어려움 · 검사는 한눈에)

찾기는 어렵고 확인은 쉽다. 이 두 가지가 따로 노는 것이 이런 문제들의 특징이다.
외판원 문제도 마찬가지다. 가장 짧은 길을 찾기는 어렵지만, '총 거리가 얼마 이하인 길이 있는가'라고 묻는다면 누가 내민 길의 거리를 더해 보기만 하면 확인돼요.

빠른 풀이가 있을까

여기서 큰 질문이 나온다. '확인이 빠른 문제는 푸는 것도 빠를까?'
어쩌면 우리가 아직 똑똑한 방법을 찾지 못한 것뿐일 수도 있고, 정말로 빠른 풀이가 없는 것일 수도 있어요.
아래에서 두 입장을 눌러 보자.

두 입장을 눌러 본다. (확인 빠름 = 풀이도 빠름? · 아무도 아직 몰라요)

놀랍게도 이 질문의 답은 아직 아무도 모른다. 전 세계 수학자와 과학자가 오래 매달렸지만 '빠른 풀이가 있다'도 '없다'도 증명하지 못했다.
이것이 컴퓨터 과학에서 가장 유명한 미해결 문제다. 그러니 누가 '쉽다'고 하면 살짝 의심해도 좋아요.

어려운 문제들

이런 문제는 하나만이 아니다. 여러 도시를 가장 짧게 도는 길, 무게 한도 안에서 가장 값진 짐을 고르는 배낭, 이웃 나라끼리 색이 겹치지 않게 지도를 칠하는 문제가 있다.
겉보기는 다 달라도 속을 보면 닮았어요. 경우의 수가 폭발하고 확인은 쉽다는 점이다.
아래에서 예를 바꿔 보자.

예를 눌러 바꾼다. (외판원 · 배낭 · 그래프 색칠, 모두 같은 결의 어려움)

이렇게 닮은 문제들이 수천 가지나 모여 있다. 신기하게도 이 가운데 하나라도 빠르게 푸는 방법을 찾으면 나머지도 모두 빠르게 풀린다.
서로 손을 잡고 있는 셈이다. 하나만 풀면 전부 풀리니 더 흥미로워요.

정리

한 줄로 모으면 이렇다. 어떤 문제는 입력이 조금만 커져도 경우의 수가 폭발해서 빠른 풀이가 아직 알려져 있지 않다.
그런데 답을 찾기는 어려워도 확인은 쉬운 경우가 많다. 그렇다면 확인이 빠르면 푸는 것도 빠를까? 이것은 아직 아무도 모르는 큰 수수께끼예요.
아래에서 차례로 눌러 정리해요.

핵심을 차례로 눌러 정리해요. (폭발 → 확인은 쉬움 → 아직 미해결)

모든 문제가 똑같이 쉬운 것은 아니다. 어떤 문제는 정말로 버겁다.
하지만 버겁다고 끝은 아니다. 다음 레슨에서는 완벽한 답을 포기하는 대신 '충분히 좋은 답'을 빠르게 찾는 영리한 방법들을 만나요.