6 ms·

P vs. NP: An Assumption That Runs the Internet

64 points by Garbage 11y ago

buzzdenver 11y ago
Routing is not the same as the Traveling Salesman problem unless you want your packets to go thru all the routers. It's a shortest path problem, which is P. P == NP does not really mean that solving is as easy is verifying the solution. The former could be O(n^4) while the latter O(1). It rather means that if a solution can be verified in a reasonable time (polinomial), then it was also possible to calculate it in a reasonable time.
modulus1 11y ago
This article seems to assume that problems in P are computable no matter the size. If it is shown NP=P, but the best algorithm we have is O(n^100), we still don't have a computer that can actually finish the computation.
andrew-lucker 11y ago
There are NP problems in network routing and analysis, but implying that shortest path is NP would be an oversimplification.
aruss 11y ago
It's a decent introduction to P vs. NP but gets a few things wrong: factoring is technically an NP problem, but it's not (known to be) NP-complete, and packet routing is a pathfinding problem rather than a TSP, which is distinctly in P. Also it should probably address the silly arguments that pop up that there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice. And the implications for security would be huge because we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not? How does parallelization affect runtime? Things become a lot messier. So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not.
- modulus1 11y ago
  > I have yet to see a convincing argument that it's not http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858 Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps. ... My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M. ... The moral is that people should distinguish between known (or knowable) polynomial-time algorithms and arbitrary polynomial-time algorithms. People might never be able to implement a polynomial-time-worst-case algorithm for satisfiability, even though P happens to equal N P.
  - mcguire 11y ago
    On the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]: "So, OK, why should you believe P≠NP? Here’s why: "Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false." [1] http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720
    - SilasX 11y ago
      I think they're agreeing on the major substantive issue, that we won't reach a world where "composing a symphony is just as easy as enjoying it" -- Aaronson, because P != NP, and Knuth, because the proof of P=NP will not provide a polynomial-time algorithm for NP-complete problems.
      - danbruc 11y ago
        This symphony thing comes up again and again but it seems pretty silly to me. Enjoying and composing a symphony requires understanding what makes a piece of music sound good to humans, undoubtedly a nontrivial problem, but is it really hard to imagine that once that got formalized one can use this information to search the space of all possible pieces of music for beautiful symphonies in a not terrible inefficient way? I don't think so.
mabbo 11y ago
The author doesn't seem to understand very well a lot of the problems he's describing.
blahedo 11y ago
> If P equals NP, then you could solve anything as easily as you could verify it. This is the core oversimplification of the article—if P=NP there's no guarantee that the solution is as easy as the verification. O(n^3) is still more expensive than O(n^2), even though both are in P.
umutisik 11y ago
A joke about P=NP: http://www.scottaaronson.com/writings/phcollapse.pdf http://www.scottaaronson.com/writings/phcollapse.pdf
- rhaps0dy 11y ago
  That was pretty good, and it would have been better for me if I knew all the classes involved. For those in the same position as I, https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy may be a good start.
bjacks 11y ago
I don't understand how verifying a TSP is any different to solving it - I.e. don't I have to do just as much work to verify that a particular solution is correct as if I was solving it from scratch? I.e. brute force?
- Dylan16807 11y ago
  The Traveling Salesman Decision Problem, the one that's NP-complete and not just NP-hard, does not ask for the lowest cost route. It asks whether there is a route cheaper than k. Verifying that is trivial, you just follow the route and compare to k.
- mdxn 11y ago
  The actual decision problem statement for TSP is "Does there exist a tour of less than length L". It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.
- ctrl_freak 11y ago
  TSP is NP-hard -- we don't know if it's in NP (that is, we don't even know if there's a polynomial time algorithm to verify whether a proposed solution is optimal). The decision problem of TSP is NP-complete: > The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. ( https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co... ) The author got this wrong in the article -- just because you can check that each house has been visited in polynomial time proves nothing.
- danpat 11y ago
  There are a few ways to ask the TSP question. One question is "give me the shortest route geometry", this problem is NP-hard and can't be verified easily, this is what you're thinking of. However, the decision version of the problem is usually phrased "Is there a tour of less than length L", and this is NP-Complete - takes a while to find the tour, but it's trivial to check if it's less than length L.
cinquemb 11y ago
When ever I see P != NP around, it reminds me of when a matrix is equal to its self adjoint, and I wonder if you use any predefined curves and treat it as a polynomial eigenvalue problem, then project it onto a lower dimensional complex space, if one can then use the solutions to generate approximately the observed ciphertext?
anon4 11y ago
A very important point is that we have very good approximations for the TSP problem when embedded in an euclidean metric space.
faragon 11y ago
There is no need for the optimal. E.g. you can solve most routing problems with >95% efficiency using heuristics with O(1) or O(log n) asymptotic time complexity.
- devilsavocado 11y ago
  Sure, but that is kind of beside the point. For most problems where the distinction between P and NP is important, the biggest being encryption, "95% efficiency" is absolutely useless.
  - faragon 11y ago
    Until a "95% efficiency" heuristic/approximation can be applied to a primality test, in that case (e.g. if someone finds a geometric heuristic for primality).
JoshTriplett 11y ago
Related: has anyone seen any good speculative fiction stories that start from the premise of a constructive, practical P=NP proof and go from there?
- bazzargh 11y ago
  There's a short story, 'Antibodies', along those lines in Charles Stross' 'Toast' collection. http://www.antipope.org/charlie/blog-static/fiction/toast/toast-intro.html http://www.antipope.org/charlie/blog-static/fiction/toast/to...
- doodpants 11y ago
  There's a movie called "Travelling Salesman" [1]. It's available on Amazon's video service. [1] http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7 http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7
justifier 11y ago
lately i've been musing on the idea that a poly np-complete algo is conciousness

64 points by Garbage 11y ago

Routing is not the same as the Traveling Salesman problem unless you want your packets to go thru all the routers. It's a shortest path problem, which is P. P == NP does not really mean that solving is as easy is verifying the solution. The former could be O(n^4) while the latter O(1). It rather means that if a solution can be verified in a reasonable time (polinomial), then it was also possible to calculate it in a reasonable time.

modulus1 11y ago

This article seems to assume that problems in P are computable no matter the size. If it is shown NP=P, but the best algorithm we have is O(n^100), we still don't have a computer that can actually finish the computation.

andrew-lucker 11y ago

There are NP problems in network routing and analysis, but implying that shortest path is NP would be an oversimplification.

aruss 11y ago

It's a decent introduction to P vs. NP but gets a few things wrong: factoring is technically an NP problem, but it's not (known to be) NP-complete, and packet routing is a pathfinding problem rather than a TSP, which is distinctly in P. Also it should probably address the silly arguments that pop up that there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice. And the implications for security would be huge because we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not? How does parallelization affect runtime? Things become a lot messier. So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not.

modulus1 11y ago
> I have yet to see a convincing argument that it's not http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858 Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps. ... My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M. ... The moral is that people should distinguish between known (or knowable) polynomial-time algorithms and arbitrary polynomial-time algorithms. People might never be able to implement a polynomial-time-worst-case algorithm for satisfiability, even though P happens to equal N P.
- mcguire 11y ago
  On the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]: "So, OK, why should you believe P≠NP? Here’s why: "Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false." [1] http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720
  - SilasX 11y ago
    I think they're agreeing on the major substantive issue, that we won't reach a world where "composing a symphony is just as easy as enjoying it" -- Aaronson, because P != NP, and Knuth, because the proof of P=NP will not provide a polynomial-time algorithm for NP-complete problems.
    - danbruc 11y ago
      This symphony thing comes up again and again but it seems pretty silly to me. Enjoying and composing a symphony requires understanding what makes a piece of music sound good to humans, undoubtedly a nontrivial problem, but is it really hard to imagine that once that got formalized one can use this information to search the space of all possible pieces of music for beautiful symphonies in a not terrible inefficient way? I don't think so.

mabbo 11y ago

The author doesn't seem to understand very well a lot of the problems he's describing.

blahedo 11y ago

> If P equals NP, then you could solve anything as easily as you could verify it. This is the core oversimplification of the article—if P=NP there's no guarantee that the solution is as easy as the verification. O(n^3) is still more expensive than O(n^2), even though both are in P.

umutisik 11y ago

A joke about P=NP: http://www.scottaaronson.com/writings/phcollapse.pdf http://www.scottaaronson.com/writings/phcollapse.pdf

rhaps0dy 11y ago
That was pretty good, and it would have been better for me if I knew all the classes involved. For those in the same position as I, https://en.wikipedia.org/wiki/Polynomial_hierarchy https://en.wikipedia.org/wiki/Polynomial_hierarchy may be a good start.

bjacks 11y ago

I don't understand how verifying a TSP is any different to solving it - I.e. don't I have to do just as much work to verify that a particular solution is correct as if I was solving it from scratch? I.e. brute force?

Dylan16807 11y ago
The Traveling Salesman Decision Problem, the one that's NP-complete and not just NP-hard, does not ask for the lowest cost route. It asks whether there is a route cheaper than k. Verifying that is trivial, you just follow the route and compare to k.
mdxn 11y ago
The actual decision problem statement for TSP is "Does there exist a tour of less than length L". It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.
ctrl_freak 11y ago
TSP is NP-hard -- we don't know if it's in NP (that is, we don't even know if there's a polynomial time algorithm to verify whether a proposed solution is optimal). The decision problem of TSP is NP-complete: > The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. ( https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co... ) The author got this wrong in the article -- just because you can check that each house has been visited in polynomial time proves nothing.
danpat 11y ago
There are a few ways to ask the TSP question. One question is "give me the shortest route geometry", this problem is NP-hard and can't be verified easily, this is what you're thinking of. However, the decision version of the problem is usually phrased "Is there a tour of less than length L", and this is NP-Complete - takes a while to find the tour, but it's trivial to check if it's less than length L.

cinquemb 11y ago

When ever I see P != NP around, it reminds me of when a matrix is equal to its self adjoint, and I wonder if you use any predefined curves and treat it as a polynomial eigenvalue problem, then project it onto a lower dimensional complex space, if one can then use the solutions to generate approximately the observed ciphertext?

anon4 11y ago

A very important point is that we have very good approximations for the TSP problem when embedded in an euclidean metric space.

faragon 11y ago

There is no need for the optimal. E.g. you can solve most routing problems with >95% efficiency using heuristics with O(1) or O(log n) asymptotic time complexity.

devilsavocado 11y ago
Sure, but that is kind of beside the point. For most problems where the distinction between P and NP is important, the biggest being encryption, "95% efficiency" is absolutely useless.
- faragon 11y ago
  Until a "95% efficiency" heuristic/approximation can be applied to a primality test, in that case (e.g. if someone finds a geometric heuristic for primality).

JoshTriplett 11y ago

Related: has anyone seen any good speculative fiction stories that start from the premise of a constructive, practical P=NP proof and go from there?

bazzargh 11y ago
There's a short story, 'Antibodies', along those lines in Charles Stross' 'Toast' collection. http://www.antipope.org/charlie/blog-static/fiction/toast/toast-intro.html http://www.antipope.org/charlie/blog-static/fiction/toast/to...
doodpants 11y ago
There's a movie called "Travelling Salesman" [1]. It's available on Amazon's video service. [1] http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7 http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7

justifier 11y ago

lately i've been musing on the idea that a poly np-complete algo is conciousness