Subject: The P vs. NP Problem

From: Omer Zak <[email-masked]>
Date: Wed, 03 Jun 2009 23:42:34 +0300

The following paper is a nice summary of opinions about this classical
computer science problem:
http://www.cs.umd.edu/~gasarch/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

---

From: Hadar Weiss <[email-masked]>
Date: Thu, 4 Jun 2009 01:05:53 +0300

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 <[email-masked]> wrote:

> http://www.cs.umd.edu/~gasarch/papers/poll.pdf<http://www.cs.umd.edu/%7Egasarch/papers/poll.pdf>
>

---

From: Omer Zak <[email-masked]>
Date: Thu, 04 Jun 2009 01:55:42 +0300

> Do you mean how to verify a solution for TSP in polynomial time?

Yes.

> "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.

Is the procedure of reduction executable in polynomial time?

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

> 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/