Re: [hackers-il] The P vs. NP Problem
- On Thu, 2009-06-04 at 01:05 +0300, Hadar Weiss wrote:
> Do you mean how to verify a solution for TSP in polynomial time?
> If that's the case, you better look at the TSP as a decision problem:Is the procedure of reduction executable in polynomial time?
> "A variant of the traveling salesman problem, where we want to know if
> there is a route of some length that goes through all the nodes in a
> certain network"
> (This variant is equivalent to the search problem - there's a simple
> reduction from the decision to the search problem)
> Now we can talk about verifying a solution to the decision problem:Why?
> 1. Make sure the route is indeed in the correct length
> 2. Verify that all the cities are visited (using some linear space)
> 3. Verify that no city is visited more than once (using some more
> small space)
> There is no need to check if it's the optimal solution - that's the
> fun part of it...
My question is simple.
Given a purported solution to the Travelling Salesman Problem, how do we
verify that it is the correct solution?
Besides checking that all the cities were visited, how do I verify that
there is no other arrangement of cities which shortens the path
travelled by the salesman? Is it possible at polynomial time at all?
> I leave you with the correctness ;)How about the original Travelling Salesman Problem?
> This verifier checks the solution in a polynomial time and therefore
> the problem is in NP.
One does not make peace with enemies. One makes peace with former
My own blog is at http://www.zak.co.il/tddpirate/
My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html