제 4 부

정말 어려운 문제 — 난해성(intractability)

다루기 힘듦(Intractability)

컴퓨터에게 조차도 너무 어려운 문제가 있을까요? 예, 있습니다. 20번째 활동에서 살펴보겠지만, 단지 대화하는 것—채팅(chatting)—조차도 컴퓨터가 할 수 없다. 컴퓨터가 말을 할 수가 없어서가 아니라, 컴퓨터가 의미있는 것을 이해하고 생각해 낼 수가 없기 때문이다. 하지만, 여기서 논의하는 정말 어려운 문제는 이런 종류가 아니다. 사실 컴퓨터가 대화를 하지 못하는 것은 아니다. 사람이 어떻게 대화를 하는지 알지 못해서, 컴퓨터에게 무엇을 수행하도록 지시할 수 없다. 이번 섹션에서 컴퓨터에게 수행 명령을 지시—프로그램 작성—하기는 쉬우나, 사람이 원하는 것을 컴퓨터가 수행하지 못하는 종류의 문제를 살펴본다. 이유는 컴퓨터가 답을 가져오는데 아마도 수백만년 시간만큼, 작업 소요시간이 너무 오래 걸린다.

제 2부 알고리즘 활동에서 컴퓨터 프로그램을 좀더 효율적으로 작성하는 방법을 살펴보았다. 이번 섹션에서 효율적인 어떠한 해결책도 알려지지 않은 문제를 살펴볼 것이다. 즉, 컴퓨터가 문제를 해결하는데 수백만년 걸리는 문제다. 그리고 나서 오늘날 컴퓨터과학에서 가장 커다란 미스터리로 남은 것과 조우한다. 어느 누구도 이러한 종류의 문제를 해결하는 좀더 효율적인 방법이 존재하는지 모른다. 아마도 어떤 사람도 좋은 방식을 아직 발견하지 못했거나 좋은 방식이 존재하지 않기 때문인지도 모른다. 둘 중에 어느 것이 맞는지 알지 못한다. 그리고 그것이 끝이 아니다. 설사 매우 다른 문제처럼 보이지만, 만약 효율적인 방법을 사용하여 문제를 해결할 수 있다면, 이러한 효율적인 방법을 전환하여 관련된 모든 문제를 해결할 수 있기 때문에 동등한 수천개 문제가 있게 된다. 이번 활동에서 이런 종류의 문제를 학습한다.

선생님에게

이번 섹션에는 활동이 세개 있다. 첫번째 활동은 지도를 색칠하고, 인접한 나라를 다른 색깔로 색칠하기는데 얼마나 많은 색깔이 필요한지 계수한다. 두번째 활동은 간단한 도로지도를 사용하는 능력이 필요하다. 거리에 아이스크림 차량을 배치해서 사람들이 너무 멀리가지 않고 아이스크림을 살 수 있게 한다. 세번째 활동은 야외활동으로 줄과 못을 사용해서 집합의 점들을 연결하는 짧은 네트워크를 구성하는 방법을 탐색한다.

복잡성(complexity)에 대한 아이디어를 실습 활동을 통해서 공감하게 된다. 말로 구술하기는 매우 간단한 문제가 해결하기에는 너무나 어려운 문제가 해당된다. 그리고, 이러한 문제가 결코 난해하지 않다. 학교 시간표 작성, 도로 건설, 매핑 등 같은 일상 생활에서 발생하는 실무적인 문제다. 컴퓨터적 토대는 각 활동 마무리에 있는 “컴퓨터 과학 핵심 개념”에 설명된 “NP-완전성(NP-completeness)”이라고 불리는 개념에 기반한다. 활동 자체는 임의 순서로 다뤄질 수 있지만, 각 섹션은 순차적으로 읽어 내려가도록 구성되었다. 마지막을 읽어 내려갈 때 즈음, 현대 컴퓨터 과학에서 가장 중요한 미해결 문제(open question)에 대한 확고한 이해를 갖게 된다.

제4부에 대한 기술명칭은 “난해성(intractability)”인데 해결하기 어려운 문제가 난해하다고(intractable) 불리기 때문이다. 당기다 끌다는 의미를 가지는 라틴어 tractare 에서 유래해서 현재는 다루기 쉬운(tractable), 휘기 수운, 유순한 이라는 의미로 사용된다. 난해한 문제(intractable problem)는 쉽게 다룰 수 없는데 이유는 답을 가져오기까지 너무나 오래 걸린다. 비밀스럽게 드릴지 모르지만, 난해성은 일상에서 매우 중요한다. 왜냐하면, 이 분야에서 돌파구가 마련되면 많은 다른 연구분야에 엄청난 파생결과가 발생한다. 예를 들어, 대부분의 암호화 코드는 어떤 문제의 난해성에 기반한다. 그래서 효율적인 해결책을 발견한 범죄자가 신나서 암호를 풀어 상업적으로 판매를 하거나 혹은 좀더 단순하게 거짓 운행 거래를 생성할 수 있다. 제5부에서 암호기법(cryptograph)에서 살펴볼 것이다.