- View SourceThe 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 - View SourceDo 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, 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,

HadarOn Wed, Jun 3, 2009 at 11:42 PM, Omer Zak <w1@...> 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

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

- View SourceOn Thu, 2009-06-04 at 01:05 +0300, Hadar Weiss wrote:
>

Yes.

>

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

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

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

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