The travelling salesman problem is still unresolved. A 26 year old claim for a solution is finally fully refuted by researchers of Centrum Wiskunde & Informatica (CWI) in Amsterdam, Université libre de Bruxelles and Friedrich-Alexander Universität Erlangen-Nürnberg. The researchers presented their findings on the Symposium on Theory of Computing 2012 (STOC ’12), this week in New York. They shared the symposium’s Best Paper Award for their work.
The hardness of the travelling salesman problem is one of the biggest unresolved problems in mathematics and computer science. The problem concerns a salesman looking for the shortest possible route through a certain area that allows him to visit every city in the area exactly once. For years mathematicians and computer scientists have been looking for an efficient solution to this problem. If this solution exists, it would mean that the famous question whether P = NP can be answered positively. The P=NP-equation states that every problem which solutions can be efficiently checked by a computer, can also efficiently be solved by a computer. If this is true, the consequences would be enormous. Complex problems in for instance planning, logistics and bioinformatics could be solved efficiently, leading to a rapid series of development in science and technology.
The P=NP problem is probably the most important problem in theoretical computer science. It is also one of the seven Millennium Prize Problems of the Clay Mathematics Institute. The institute offers a one million dollar reward to the person who finds a solution to the problem. Most experts expect that P≠NP. In a recent survey by the University of Maryland that covered 100 leading researchers in mathematics and computer science, only 9 researchers believe that proof for P=NP will be found, 61 believe that it will be disproved and 30 were not sure or did not give a definite answer.
Nevertheless, claims for proofs of P=NP regularly surface. Usually they can be easily refuted, but sometimes they can’t. In their paper, a group of Dutch, German and Belgian researchers refute a proof suggested in the 80’s. ‘In 1986 Canadian mathematician Ted Swart claimed that he had resolved the travelling salesman problem by means of a so-called linear program,’ CWI researcher Ronald de Wolf says. ‘This caused quite a stir in the mathematical community, but soon nobody turned out to be able to verify the results. A year later, computer scientist Mihalis Yannakakis proved that symmetric linear programs such as Swart’s in principle cannot solve the travelling salesman problem efficiently. But the suggestion to use linear programs remained. Now, 26 year after Swart’s claim, we proved that linear programs are altogether unable to solve the problem efficiently, even if they are non-symmetric.’
More information:
- S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds.
- Website Ronald de Wolf (CWI)
Image: travellingsalesman.org
