Russky solves Traveling Salesman Problem

[BaalChatzaf]

I just caught this:

The apparent breakthrough was achieved by L. G. Khachian, and was published in a Soviet scientific journal, Doklady, last January. Few people in the West read the journal and it was only after rumours of the discovery circulated at a conference in Germany that anyone in the mathematical world at large had even a hint that someone had come up with an answer to what is known in the trade as the “travelling salesman” problem.

Way to go, L.G. Khacian!!!!!

[merjet]

http://en.wikipedia.org/wiki/Travelling_salesman_problem

[Brant Gaede]

Taken literally the TSP is no problem at all. It's no problem for a salesman for he's going one way or the other even if haphazardly. It's a problem for mathematicians expressed metaphorically. Maybe its solution is valuable for airplane or space flights or a scientific investigation, but not for an ignorant, mathematically deficient sod as myself.

--Brant

not even a travelling salesman

[BaalChatzaf]

Taken literally the TSP is no problem at all. It's no problem for a salesman for he's going one way or the other even if haphazardly. It's a problem for mathematicians expressed metaphorically. Maybe its solution is valuable for airplane or space flights or a scientific investigation, but not for an ignorant, mathematically deficient sod as myself.

--Brant

not even a travelling salesman

"solving the T.S.P." means doing it on polynomial time on the set of stops. If there are N stops then the number of steps required is a polynomial function of N. This is to be distinguished from exponential time. Most of the popular combinatorial programs have be show to be NP-complete. T.S.P. is NP-hard. If this proof the Russian gave is valid and generalizable it may lead to a solution of P = NP which is the biggest open problem in computation theory.

Ba'al Chatzaf