골드바흐가 주장한 TSP 알고리즘 :

http://gall.dcinside.com/board/view/?id=mathematics&no=230989


1. TSP (Traveling Salesman Problem)는 그래프가 주어지고 그래프의 edge 위에 거리가 주어졌을때, edge의 거리 합을 최소로하는 모든 정점을 방문하는 cycle을 찾는 문제를 말한다.


TSP의 가장 일반적인 form은 그래프가 주어졌을때, 각 edge 위에 거리가 정의되어있는 경우를 말한다. 

- 만약 두 edge (u,v)와 (v,u)의 거리가 항상 같게 주어진다면 이 경우를 symmetric TSP라고 하는데, 사람들이 주로 TSP라고 말한다면 이것을 뜻한다. 예를 들어서 minimum spanning tree를 이용하는, 최적해보다 많아야 거리합이 2배 이하가 되는 아주 쉬운 근사 알고리즘이 있다.

- 두 edge (u,v)와 (v,u)의 거리를 다르게 정의하는 경우는 Asymmetric TSP라고 부르고, symmetric TSP보다 더 일반적인 경우라서 훨씬 어렵다. 이 경우의 효율적인 근사 알고리즘은 오랫동안 open이었는데 지난달에 간신히 최적해보다 많아봤자 상수배 차이나는 근사 알고리즘을 찾을수 있게 되었다. (https://arxiv.org/abs/1708.04215)

- Euclidean TSP란, R^2 위에 n개의 점들이 주어졌을때 두 점 사이의 거리가 실제 R^2 위에서의 거리로 정의된 complete graph의 TSP를 말한다. 이는 TSP의 가장 약한 variant 중 하나이다. 일반적으로 TSP의 그래프에서 정의되는 거리가 metric의 공리를 만족할 이유가 전혀 없기 때문이다.

Euclidean TSP (ETSP) 의 경우 가장 약한 variant 중 하나이고, 실제로 거의 최적해와 아주 가깝게 근사할 수 있다. (전문용어로 서술하면 euclidean TSP는 PTAS에 해당한다.) 2010년에 Arora와 Mitchell이 Euclidean TSP가 PTAS에 해당한다는것을 증명하여 Godel prize를 수상하였다. (Godel prize는 theoretical computer science의 최고 권위의 상이다.)





2. 먼저 골드바흐가 TSP라고 생각한건 TSP 중에서 가장 약한 variant 중 하나인 Euclidean TSP이다. TSP 중에서 가장 쉬운 variant이지만 여전히 NP-hard로 취급되는 문제이다. 따라서 골드바흐의 말이 참이라면, P=NP가 성립한다. 그리고 2010년에 Arora와 Mitchell이 PTAS인것을 증명해서 괴델상을 수상한 업적을 뛰어넘게 된다.


골드바흐가 주장한건 결국 convex hull을 구한다음에, convex hull 내에 포함되어있지 않은 점 중에서 포함시킬때 cost 증가가 가장 적은 애들을 넣는 방식인데, 이 방식은 직관적으로 가장 쉽게 생각할 수 있는 방식이다. Convex hull insertion method라고 부른다.


하지만 실제로 알고리즘이 그렇게 효율적이지는 않다. 이 알고리즘은 최적해의 3배 이내의 답을 보장하지만, 문제는 위에서 minimum spanning tree를 이용한 훨씬 쉬운, 최적해의 2배 이내의 답을 보장하는 거의 trivial한 알고리즘이 이미 존재하기 때문이다. 게다가 이것은 euclidean TSP 외에도 symmetric TSP에 대해서도 모두 적용가능한 근사알고리즘이다. 알고리즘을 약간 개선하면 2배를 1.5배로 줄일 수 있다.


골드바흐가 '최적해'라고 주장하였지만, 실제로 최적해가 아니다. 이 알고리즘의 최악의 경우를 분석해놓은 아래의 paper가 있다.

http://www.sciencedirect.com/science/article/pii/016763779390082R?via=ihub


여기서 주장하는건 결국 Convex hull insertion method을 썼을때 최적해보다 적어도 3 - O(n^{-1/2})배 안좋은 임의의 정점 n개로 구성된 example을 항상 찾을 수 있다는 것이다. 

결국 어떻게 발버둥을 치든간에, 위에서 말한 minimum spanning tree를 이용한 단순한 것보다 알고리즘이 거의 항상 안 좋게 된다.


본인은 최적해라고 "주장"했을 뿐이지, 이것이 최적해라는 논리적인 이유는 전혀 찾을수 없다. 그리고 이미 최적이 아니라는 것을 증명해놓은 위의 결과가 있다.






3. 결론

내가 항상 하고 싶은 이야기는, 논리적인 뒷받침이 전혀 없는 주장은 증명이라고 할수도 없으며 아무런 의미가 없게 된다는 뜻이다. 어찌보면 이것은 시간낭비에 가깝다. 


과거의 수많은 유사수학자들, 임의의 각의 삼등분이 가능하다고 주장하시는 분이나 페르마 대정리를 증명하였다고 몇년간 주장하였던 어느 분의 사례를 미루어보면, 그 분들의 공통점은 증명에서 어떤 명제를 주장하는데 그것에 대한 뒷받침이 제대로 마련되어있지 않다는 점이었다. 


언뜻 보면 직관적으로 당연해 보이지만 실제로 틀리는 경우가 수없이 많다. 자기 자신을 수학도라고 생각한다면 항상 이 점에 대해서 경계하고 자신의 증명에 대해서 비판적으로 접근해야한다. 

남이 자기 증명에 대해서 비판적으로 접근해주기를 바라고, 자기 스스로는 몇년동안 그 의무를 방치하는 것은 수학도로서 옳은 자세가 아니다.