안 풀리는 문제도 있을까

경우의 수가 폭발해요

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

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

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

풀긴 어렵지만 확인은 쉬워요

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

답 후보를 눌러보면 확인은 금방이에요. (찾기는 어려움 · 검사는 한눈에)

찾기는 어렵고
확인은 쉽다.
이 두 가지가 따로 노는 게
이런 문제들의 특징이에요.
외판원 길도 똑같아요.
가장 짧은 길을 찾는 건 어렵지만,
'이 길의 총 거리는 얼마' 하고
주어진 길을 재보는 건
그냥 더하기 몇 번이면 돼요.

빠른 풀이가 있을까요

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

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

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

어려운 문제들

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

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

이렇게 닮은 문제들이
수백 가지나 모여 있어요.
신기하게도 이 중 하나라도
빠르게 푸는 방법을 찾으면,
나머지도 다 빠르게 풀려요.
서로 손을 잡고 있는 셈이죠.
그래서 더 흥미로워요.
하나만 풀면 전부 풀리니까요.

정리

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

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

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