Re: The P vs. NP Problem

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:
"A variant of the traveling salesman
problem<http://en.wikipedia.org/wiki/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)#Examples
(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:
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...

I leave you with the correctness ;)
This verifier checks the solution in a polynomial time and therefore the
problem is in NP.

Hope that helps (and I didn't do any mistake).
Thanks for the article,
Hadar


On Wed, Jun 3, 2009 at 11:42 PM, Omer Zak <w1-W6cp89mEpD1mR6Xm/[email protected]> wrote:

>
>
> The following paper is a nice summary of opinions about this classical
> computer science problem:
> http://www.cs.umd.edu/~gasarch/papers/poll.pdf<http://www.cs.umd.edu/%7Egasarch/papers/poll.pdf>
>
> And as I was reading it, it occurred to me that it is not obvious for me
> how to check a solution to the Travelling Salesman Problem.
>
> Suppose you compute the shortest path for a travelling salesman.
> How do you actually check this result?
>
> --- Omer
>
> --
> MS-Windows is the Pal-Kal of the PC world.
> 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
>
>  
>