Loading ...
Sorry, an error occurred while loading the content.

Re: [hackers-il] The P vs. NP Problem

Expand Messages
  • Omer Zak
    ... Yes. ... Is the procedure of reduction executable in polynomial time? ... Why? My question is simple. Given a purported solution to the Travelling Salesman
    Message 1 of 3 , Jun 3, 2009
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.