05. 하나의 질문으로는 충분하지 않다!

<알고리즘 행성 여행자들을 위한 안내서>

단 하나의 어려운 문제로는 많은 것을 시작할 수 없다. 암사자의 몸에 사람의 얼굴을 가진 테베의 스핑크스에게는 훌륭한 질문이 딱 한 개밖에 없었다. 그래서 오이디푸스가 수수께끼의 정답을 맞히자 수치심에 못 이겨 절벽에서 뛰어내려 죽음을 맞았다. 우리가 정말로 원하는 것은 ‘어려운 문제를 구성하기 위한 원칙’이다. 여기에서 말하는 한 질문 혹은 한 문제는 두말할 것 없이, 늘 무한한 양으로 응용할 수 있지만 본질은 똑같은 질문과 문제를 의미한다.

알렉산더 대왕은 고르디우스의 매듭을 그냥 칼로 끊어버렸다. 물론 그가 그렇게 했다고 해서 수수께끼를 풀어냈다고는 볼 수 없다.

<슈퍼마리오>에서 한 레벨을 클리어하기 위해선 친구들에게 물어보거나 인터넷을 검색하면 된다. 그렇다고 해서 게임이 시시하게 끝나진 않는다. <슈퍼마리오> 같은 점프 앤 런(Jump and Run) 게임의 구성 요소와 장애물, 그리고 그 장애물을 극복하기 위해 모으는 파워-업 방식을 활용하면 새롭고도 더 어려운 레벨을 만들어낼 수 있다. 임의의 레벨에서 배관공 마리오에게 길이 있는지 없는지를 결정하는 문제가 바로 그런 문제 집합이다.

이런 식의 문제 집합에는 모두 임의의 크기의 문제들이 포함돼 있다. 가장 작은 문제들은 쉽게 풀 수 있다. 예를 들어, 한 대의 열차가 오직 두 개의 역만 오간다고 할 경우, 언제든 어렵지 않게 열차운행표를 만들 수 있다. 좀 더 커다란 문제를 푸는 것은 좀 더 번거롭다. 이것은 단순한 문제 집합인 경우에도 마찬가지다. 유럽을 가로지르는 최단 경로를 찾는 과제는 에어랑엔 같은 도시에서 똑같은 과제를 수행할 때보다 훨씬 더 번거롭다. 문제 집합의 난이도를 결정하는 것은 문제의 크기와 더불어 비용이 얼마나 크게 증가하느냐 하는 것이다. 정말로 어려운 문제라면 그 증가 속도는 폭발적이다.

폭발적으로 비용이 증가하는 알고리즘으로만 풀 수 있는 문제라면, 그 문제는 매우 어려운 것임이 틀림없다. 폭발적인 비용 증가는 좀 더 커다란 문제와 그 문제를 풀기 위한 좀 더 커다란 원천 간의 힘의 비율변화에 본질적으로 영향을 미친다. 최적의 지하철 운행시간표를 고안하는 것은 어려운 문제다. 그럼에도 불구하고 베를린 지하철 운행시간표 짜기 같은 문제도 충분히 풀어낼 수 있다. 한 도시의 지하철 노선이 12개 더 늘어나면 이 문제는 12배가 아니라 1조 배 더 번거로워진다는 것을 고려할 때, 이는 결코 쉬운 일이 아니지만 말이다.

놀랍게도 바로 이런 점 때문에 우리가 안심할 수 있는 상황이 만들어지기도 한다. <슈퍼마리오> 역시 어려운 문제다. 레벨 하나를, 좀 더 전문가적인 표현을 써서 한 엔티티(entity)를 풀어낼 소박한 수단이 없다면, 40개의 장애물로 이뤄진 엔티티는 이보다 훨씬 더 많은 수십억, 수백억, 수천억 개의 강력한 수단이 있어도 풀 수 없다. 미국 국가안보국(NSA)이라 해도 절대 풀 수 없다.

장기적인 시각으로 볼 때, 어려운 문제들 앞에서 우리는 모두 평등하다. 물론 다양한 알고리즘 적용 기술과 강력한 컴퓨터를 활용하는 전문가들은 문외한들보다 처지가 좀 더 나을 것이다. 하지만 좀 더 커다란 다량의 엔티티는 전문가들 또한 풀지 못한다. 어려운 질문의 경우엔 뭔가를 약간 더 넣어서 조금만 더 확대해도, 사실상 해답을 찾아내는 것이 불가능해진다.