Ron Graham Gives a Talk
Is the traveling salesman problem np-complete
Ron Graham is part mathematician, part computer scientist, part juggler, part magician–he is one of the most talented people I know. He has done terrific work in the theory of computation, and today I will talk about just one of his many great results.
Speaking of talks I would like to share one story about ”talks” that involves Ron. I know others, but let’s save those for a future post. This one is probably famous–especially among those who saw it. The talk concerns the work that I will discuss today–his proof that the Eucildean Traveling Salesman Problem is NP-hard. He presented this work at the ACM STOC Conference back in 1976. The work was joint with Mike Garey and David Johnson, who are the authors of the famous book ”Computers and Intractability: A Guide to the Theory of NP-Completeness”.
In 1976 Graham used an overhead projector to present his talk: this was way before Powerpoint. Then, talks were prepared by writing on clear plastic transparencies called slides. The slides were placed on top of a flat glass surface of a projector, under which was a very bright lamp: the light passed through the slide and reflected off a mirror and then onto the screen. In this way the speaker could see the slide and the audience could see the slide’s image projected on the screen.
Sometimes people would point to places on the slide with a pen or even with their fingers in order to highlight some key part of the slide. This would, of course, appear on the screen as a dark shadow, since they pen or figure were opaque. Pointing in this manner could be annoying if done poorly, but it was a common practice. Today people prefer laser points, in 1976 just as there was no Powerpoint, there were no laser pointers. I imagine then a laser would have cost thousands of dollars and been the size of a small desk.
The proof that the Euclidean Traveling Salesman Problem could encode all of NP required a “gadget”. Often in this type of proof a gadget was required. This result was no different, and Ron used a small piece of cardboard to represent the gadget, since the gadget was a geometric shape. He could move his gadget around the slides to highlight important parts of the construction. One advantage back then was that speakers could use two projectors, each projector could have a different slide on it. This was extremely useful as a speaker could leave a complex slide up while he presented the next one. Note, we have lost this ability in today’s presentations: two steps forward, one step backwards.
Ron was doing exactly this. He had two projectors going and was well into his talk when a miracle happen. A miracle. He was moving the cardboard piece around one slide: you could see on the screen not only the piece but his fingers that were moving it. He then calmly walked over to the second projector to present another slide. But his fingers were clearly still on the first projector. I remember vividly how it slowly dawned on the audience that the fingers on the first projector were not Ron’s. They were fake. It was a great trick and caused an uproar of laughter. Very neat.
A Problem with The Traveling Salesman Problem
Graham’s paper proved that the Euclidean Traveling Salesman Problem (TSP) was NP-hard. But it left open whether the problem was NP-complete. The difficulty hinges on a beautiful open problem that appears to still be open over thirty years later. The problem is this: Can we tell whether or not
is true in polynomial time? Here and are integers. Let’s call this problem the sum of squares problem (SSP). If SSP could be solved in polynomial time then TSP would be in NP and so it would be NP-complete. Recently, Michal Goemans posted this problem on the website called the problem garden. This is a site that is compiling a list of open problems for mathematics and for theory. Take a look at it. Even better post your open problems there. Even even better solve some of the open problems. By the way, Goemans also pointed out that this problem is of importance to our understanding of semi-definite programming.
Why is SSP Hard?
I just got a great question that I decided to add to the post. The question was: “why is SSP hard?” For any integer we can compute the value of to bits of precision in time polynomial in . So why not just compute all the square roots to high precision and see if the sum of the approximations are less than ? The answer is that we cannot show that a sum like
could not be almost equal to . We cannot show that it cannot be extremely close to . This is the reason the problem is still open, without a bound on the number of bits needed to distinguish the sum of the squares from , there can be no polynomial time algorithm.
There has been some partial results on the sum of square problem (SSP). First, there are results from computational geometry that has shed some light on related questions. A typical result is to look at how close the following can be to zero:
See the following for some recent results.
Second, there are some very pretty results by Eric Allender and his co-authors on a complexity approach to the SSP. They show that the problem is in which is the counting hierarchy. I will not go into details today, but will discuss these results in a future post.
An Exact Sum of Squares Problem
I would like to present a result that uses a very important technique due to Zhi-Zhong Chen and Ming-Yang Kao. They used the method in a great paper Reducing randomness via irrational numbers. I love this paper and will definitely be discussing it in the near future in more detail.
I will present their method as a tool for solving the exact sum of square problem (ESSP): this is the problem of whether or not
where are positive or negative integers and are only positive integers. The problem is more general than SSP, since we allow coefficients on the square roots; its simpler since we only ask that you determine whether or not the sum is exactly equal to . The technology that Chen and Kao have can only work for equalities, it appears not be of any use for inequalities. I say appears–perhaps there is a clever way to extend their method to inequalities. I do not see how, but perhaps you will.
There are algorithms for the ESSP. See this for details. The reason I wanted to show you the Chen-Kao idea is that it potentially is a very useful “trick”. You may be able to use this trick in many other contexts where others methods do not work.
Their method uses some basic facts from field theory and from the theory of algebraic numbers. If you do not know this there are many good places on the web to pick up the basics. See this for a list of sites of this topic. Perhaps the lesson for us is that often classic mathematics can make important contributions to the design of algorithms.
I think the best way to present their idea is through a simple example: suppose that
This is a toy example is so its easy to determine that it is not If you calculate it you will get about –not too hard to see that its non-zero. But consider the following number
The value of is about . Clearly, it is easier to calculate to low precision and see that its non-zero.
The first observation is that if and only if . The reason is that is a conjugate of . Algebraic numbers have conjugates and one conjugate is zero if and only if all the conjugates are zero. Moreover, in the case of numbers that are sums of square roots conjugates are easy to determine: in general the numbers and are conjugates.
Thus, if we are testing for zero we can use any conjugate that we wish: one is as good as another. The second observation is that often conjugates can have wildly different absolute values. We just gave an example where one was over times larger than the other. Chen and Kao can prove that this is the typical situation. For a more precise statement look at their paper, but the key insight is that most of the conjugates will be relatively large. Thus, to solve an ESSP first pick a random conjugate of the sum of squares that you wish to test; then compute the sum to a polynomial number of bits of accuracy. If the answer is small, then say the sum is exactly ; otherwise, say its non-zero. The probability that this works is quite high. Very neat idea.
For those who want a bit more details here goes. The number not only is a algebraic number but was an algebraic integer. The norm of usually denoted by must be at least unless is zero. But the norm is just the product of all the conjugates of . An easy argument then shows that since the absolute values of all the conjugates are not too large, there cannot be too many small conjugates.
The main open problem is to show that the SSP can be done in polynomial time. However, this is over-kill: you actually only need to show that the SSP can be done in nondeterministic polynomial time. This would be enough to show that TSP is NP-complete. This is a simple observation, yet I do not know of any results that have tried to exploit this insight. Perhaps, you can use it to solve Graham’s original problem.
A second even smaller observation is this: consider a SSP,
that arises from a TSP problem. It this case the square root’s arise from the calculation of Euclidean distances. If one point is and other is , then their distance is
After clearing denominators the values of will be special integers. In particular, they will always be the sum of two squares. Fermat essentially proved that is represented as the sum of two squares if and only if in the prime factorization of , every prime of the form occurs an even number of times. The final thought today is can we exploit this fact? Can the special nature of the square roots be useful?