BaalChatzaf Posted November 2, 2014 Share Posted November 2, 2014 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!!!!! Link to comment Share on other sites More sharing options...
merjet Posted November 2, 2014 Share Posted November 2, 2014 http://en.wikipedia.org/wiki/Travelling_salesman_problem Link to comment Share on other sites More sharing options...
Brant Gaede Posted November 2, 2014 Share Posted November 2, 2014 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.--Brantnot even a travelling salesman Link to comment Share on other sites More sharing options...
BaalChatzaf Posted November 2, 2014 Author Share Posted November 2, 2014 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.--Brantnot 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 Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now