얼음길

지금까지 다뤄온 네트워크는 최소 스타이너 트리(minimal Steiner trees)다. 트리(tree)라고 불리는 이유는 순환(cycle)이 없기 때문이다. 마치 실제 나무 가지는 분기되면서 자라지만 합쳐지거나, 합쳐진 것이 다시 함께 자라 뻗어나가고 하지 않는다. “스타이너(steiner)” 트리라고 불리는 이유는 새로운 지점(스타이너점)이 나무가 연결할 원래 지점에 추가되기 때문이다. “최소”라고 불리는 이유는 모든 지점을 연결하는 최소 네트워크를 갖기 때문이다. 진흙도시(활동 9)에서 전체 길이가 최소가 되도록 지점을 연결하는 네트워크가 최소생성나무라고 학습했다. 스타이너 > 트리는 다른 것은 동일하고 새로운 점이 추가된다는 것만 차이점이 된다.

활동 14에서 최소생성나무(minimal spanning tree)를 찾아내는 매우 효율적인 알고리즘—욕심쟁이 알고리즘으로 두개의 가장 가깝지만 아직 연결되지 않은 점을 반복적으로 연결해 나감—이 존재하지만, 최소 스타이너 트리 문제에는 일반적으로 효율적인 해답이 없다는게 흥미롭니다. 스타이너 트리는 좀더 어려운데 이유는 어디에 추가 지점을 추가할지 결정해야 하기 때문이다. 사실 다소 놀라운 점은 스타이너 트리 문제에서 가장 어려운 부분이 스타이너점이 위치할 정확한 장소를 결정하기 보다, 대략 어느 지점에 스타이너점을 위치할 것인가 이것이 관건이다. 예를 들어, 두번째 사례에서 두가지 해답 사이의 차이가 된다. 새로운 점을 어디에 찍을 것인가를 알게된다면, 최적 지점을 찾으려고 미세 조정하는 것은 상대적으로 단순하다. 비누막 사례는 매우 효과적으로 작업을 수행하고, 컴퓨터도 마찬가지로 그렇게 할 수 있다.

최소 스타이너 트리를 찾아내는 것이 전화 통신 산업에서 큰 비용절감과 연관된 이야기의 일부분이다. 1967년 이전, 미국 기업고객이 매우 큰 사설 전화 네트워크를 운영했을 때, 전화 회사에서 회선을 임대했다. 비용이 청구되는 금액은 얼마나 회선이 사용되었냐에 따라 과금이 결정되는 것이 아니라 최소 네트워크 기준으로 과금이 결정되었다. 전화 회사가 로터리 루트를 사용하기 때문에 고객은 추가 비용을 지불하지 말아야 하는 것이 이유다. 원래, 얼마를 청구금액을 계산하는 알고리즘은 최소신장트리를 결정하고 산출하었다. 하지만, 1967년경 주요 허브 3개를 소유한 항공기 회사 고객이 주목한 점이 하나 있다. 만약 중간 지점에 네번째 허브가 있다면, 전체 네트워크 길이를 줄일 수 있다는 점이다. 어쩔 수 없이 스타이너점을 전화 교환지점에 놓는다면, 길이가 짧아져서 전화 회사가 청구금액을 낮춰야 했다. 특정 배치조합에서 최소 스타이너 트리가 5% 혹은 10% 정도 최소신장나무보다 짧을 수 있지만, 금액이 매우 큰 경우 유의미한 절감금액이 된다. 스타이너 트리 문제는 종종 최단 네트워크 문제(shortest network problem)라고 불리는데 이유는 지점을 연결하는 최단 네트워크를 찾아내는 것과 관련되기 때문이다.

앞선 두가지 활동 (지도 제작자 퍼즐과 관광 마을)을 다뤄보셨다면, 최소 스타이너 트리 문제가 NP-완전 이라는 말이 놀랍지 않을 것이다. 장소 개수가 증가함에 따라, 스타이너점을 찍을 잠재 위치 > 개수도 증가한다. 따라서 모든 가능한 조합을 찾아보는 것은 기하급수적으로 늘어나게 된다. 이것이 수천개의 문제 중의 또다른 하나고, 지수시간 검색이 가장 최선인지, 혹은 아직 찾지 못한 다항시간 알고리즘이 존재하는지 알려져 있지 않다. 하지만, 알려진 것은 다음과 같다. 만약 이 문제에 지수시간 알고리즘이 발견된다면, 그래프 채색과 최소 지배 집합을 찾는데 다항시간 알고리즘으로 변환할 수 있다는 것이다. 그리고, NP-완전에 속하는 모든 다른 문제도 또한 포함된다.

앞선 활동 말미에 NP-완전(NP-complete)의 “NP”는 “non-deterministic polynomial”의 약자고 “완전(complete)”는 만약 다항시간 알고리즘이 NP-완전 문제 중 하나에서 발견된다면, 다른 모든 문제에 > 변환해서 다항시간 알고리즘으로 적용할 수 있다는 것이다. 다항시간에 해결될 수 있는 문제 집합을 P 라고 부른다. 그래서, 핵심적인 질문은 NP-완전 문제에 다항시간 알고리즘이 존재하는냐?& mdash;다른 말로, P=NP?. 이 문제에 대한 정답은 알려져 있지 않고, 현대 컴퓨터 과학의 가장 큰 미스터리 중의 하나로 남아 있다.

다항시간 알고리즘이 존재하는 문제— 설사 알고리즘이 매우 느릴지라도—는 다룰 수 있다(“trackable”)고 한다. 그렇지 못한 문제는 다룰 수 없다(“intractable”)고 한다. 왜냐하면, 컴퓨터가 얼마나 빠르든지 관계없이, 얼마나 많은 컴퓨터를 동원하든지 관계없이, 문제의 크기가 조금만 커져도 실무에서 해결할 수 없다는 것을 의미하기 때문이다. 지도 제작자 퍼즐, 관광 마을, 얼음길을 포함한 NP-완전 문제가 다룰 수 있는지 없는지 알려져 있지 않다. 하지만, 대부분의 컴퓨터 과학자는 NP-완전 문제에 다항-시간 알고리즘이 발견될 것이라는데 회의적이다. 그래서 문제가 NP-완전이라고 증명하는 것이 문제가 태생적으로 다룰 수 없는 문제라는 강한 증거로 간주된다.

효유적인 알고리즘을 찾을 수 없을 때 무엇을 해야 할까요: 세가지 가능한 방법

직장 상사가 최적 솔류션을 가진 효율적인 알고리즘을 고안해 내라고 합니다. 하지만 효율적인 알고리즘을 찾을 수 없다면 여러줌은 무엇을 하실건가요? 스타이점을 도입해서 항공회사가 네트워크 비용을 절약한 사실이 있듯이 분명 그럴 수 있습니다. 만약 최적 솔류션을 도출하는 효율적인 알고리즘이 없다는 것을 증명할 수 있다면, 매우 좋을 것이다. 하지만, 컴퓨터과학에서 이와 같은 부정적인 결과를 증명하는 것은 매우 어렵다. 그리고 누가 알겠는가 좀더 똑똑한 프로그래머가 장래에 나와서 문제를 해결하는 아무도 생각하지 못한 기법을 생각해낼지 말이다. 그래서 불행하게도 어떤 효율적인 알고리즘도 가능하지 않다고 말할 수 있는 범주에 있을 것 같지는 않다. 사실 문제는 다룰 수 없는 것이 맞다. 하지만, 만약 다루는 문제가 NP-완전이라는 것을 보일 수만 있다면, 사실 연구소에서 수천명의 연구원들이 여러줌의 것에 상응하는 다른 문제를 풀기 위해서 작업중이고, 효과적인 해결책을 찾아내는데 실패했다. 이런 사실이 여러분에게 보너스가 되지는 않는다. 하지만, 여러분을 곤경에서 풀어줄 것이다. 물론, 실생활에서 여전히 이들 문제에 대한 답을 찾을 필요는 있다. 이런 경우 사람들은 보통 휴리스틱(heuristics)으로 관심을 돌린다. 휴리스틱 알고리즘은 최적해를 보장하지는 않지만, 최적해와 비교하여 약간 차이가 있는 해결책을 제시한다. 휴리스틱 알고리즘은 매우 빠르고, 최적해를 찾지 못하는데 드는 낭비가 매우 적다. 그래서 실무에서 적용하여 사용하는데 충분하다. 좀더 나은 시간표와 좀더 나은 네트워크나 도로 건설 배치가 있다는 것을 알게되면 약간 실망스러울 뿐이다.

추가 읽기

만화는 Garey와 Johnson이 저술한 고전 “Computers and Intractability”에서 가져왔다.

1984년 6월 과학 아메리카 “Computer recreations” 칼럼에 비눗방울을 사용하여 스타이너 트리를 어떻게 만드는지에 대한 간략한 기술이 있다. 정렬을 위한 스파게티 컴퓨터, 그래프에서 최단 경로를 찾는 고양이 요람, 소수인지 알려주는 빛과 거울 장치도 함께 실려있다. Dewdney가 저술한 Turing Omnibus 책에도 아날로그 컴퓨터에 관한 별도 장으로 실려있다.