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

The P vs. NP Problem

Expand Messages
  • Omer Zak
    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
    Message 1 of 3 , Jun 3, 2009
    View Source
    • 0 Attachment
      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
    • Hadar Weiss
      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
      Message 2 of 3 , Jun 3, 2009
      View Source
      • 0 Attachment
        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, 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@...> 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


      • 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 3 of 3 , Jun 3, 2009
        View Source
        • 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.