Re: 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?

Yes.

> If that's the case, you better look at the TSP as a decision problem:
> "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"
> http://en.wikipedia.org/wiki/NP_(complexity)#Exampleswww.
> (This variant is equivalent to the search problem - there's a simple
> reduction from the decision to the search problem)

Is the procedure of reduction executable in polynomial time?

> Now we can talk about verifying a solution to the decision problem:
> 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...

Why?
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 ;)
> This verifier checks the solution in a polynomial time and therefore
> the problem is in NP.

How about the original Travelling Salesman Problem?

                                                    --- Omer
-- 
One does not make peace with enemies.  One makes peace with former
enemies.
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