6 ms·

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

by 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.
      - deleted 11y ago
        [deleted]
      - eru 11y ago
        That's not too surprising. Most NP-hard problems are pretty tractable in practice.
- devilsavocado 11y ago
  But is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bit problem in NP space in n^M steps. Knuth himself prefaces his argument by saying that it is naive! His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.
  - algorias 11y ago
    The argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all those problems are clearly in NP.
    - baddox 11y ago
      The time hierarchy theorem does not state that there are NP-complete problems that cannot be solved in polynomial time. If it stated that and was well-accepted, then there would be no P ?= NP mystery.
      - algorias 11y ago
        Correct, but I didn't claim what you are refuting. I just said that there is no upper bound to "how polynomiallly hard" a problem can get, i.e. Knuths intuition is wrong.
        baddox 11y ago
        Look at the quote. Knuth is explicitly only talking about NP problems.
dllthomas 11y ago
"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." That n^100 doesn't happen in practice might very well be selection bias. Perhaps humans are really bad at finding solutions that genuinely require polynomial work greater than O(n^4) [see note 1]. In fact, if P=NP, that would explain why we haven't thus-far found the polynomial time algorithms for any NP-complete problems. "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?" That doesn't seem materially different than having to pick key lengths. There is some amount of work you expect to be beyond what your opponents could theoretically muster. Pad a bit for safety. "So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not." We're using NP as a proxy for "provably different lower bound on checking versus finding". It's not a bad proxy, but having an actual proof of lower bound should be even better whether or not it is exponential, provided there's a sufficient gap to make realistic key sizes useful. [1] Edited to add: As pointed out to me below, there are plenty of examples of O(n^k) with arbitrarily high k. This certainly undermines my speculation about human capabilities. At the same time, it means it does happen in practice.
- spooningtamarin 11y ago
  There are plenty of algorithms with n^k where k>4, just not useful ones. Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that seem very real, and solutions (algorithms) definitely show very lovely interaction of several different areas of research, problem solving skills at its finest. http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...
  - dllthomas 11y ago
    Thanks! That weakens my speculation about human capabilities, though the fact that it deserves calling out as "problem solving skills at its finest" seems to leave me some wiggle room ;) To be honest, I'm not sure how to quantify the relative populations of higher-exponent and lower-exponent found algorithms, and if there is a skew some of that might well be due to the decreased attention to the space of higher exponent algorithms due to lower expected usefulness...
Dylan16807 11y ago
> Is n^100 secure, but n^99 not? Is 128 bits secure, but 127 not? At some point you have to arbitrarily pick a threat model. Pick a budget, a number of decades of Moore's law, and how big of an extra buffer you want. Then pray there are no gaping algorithmic flaws. This is the same whether you're looking at O(n^7) or O(2^n). The closer brute forcing gets to normal use, the worse your engineering tradeoffs have to get. But there's no magic number where crypto fails. It just slowly becomes less practical in more situations. If brute force time is at least the cube of encryption time, you barely have to worry about it being P.
baddox 11y ago
> 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? That doesn't sound right. After all, there's already an arbitrarily smooth continuum between polynomial-time and exponential-time algorithms. See quasipolymomial or sub-exponential algorithms.

by aruss 11y ago

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.
    - deleted 11y ago
      [deleted]
    - eru 11y ago
      That's not too surprising. Most NP-hard problems are pretty tractable in practice.
devilsavocado 11y ago
But is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bit problem in NP space in n^M steps. Knuth himself prefaces his argument by saying that it is naive! His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.
- algorias 11y ago
  The argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all those problems are clearly in NP.
  - baddox 11y ago
    The time hierarchy theorem does not state that there are NP-complete problems that cannot be solved in polynomial time. If it stated that and was well-accepted, then there would be no P ?= NP mystery.
    - algorias 11y ago
      Correct, but I didn't claim what you are refuting. I just said that there is no upper bound to "how polynomiallly hard" a problem can get, i.e. Knuths intuition is wrong.
      - baddox 11y ago
        Look at the quote. Knuth is explicitly only talking about NP problems.

dllthomas 11y ago

"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." That n^100 doesn't happen in practice might very well be selection bias. Perhaps humans are really bad at finding solutions that genuinely require polynomial work greater than O(n^4) [see note 1]. In fact, if P=NP, that would explain why we haven't thus-far found the polynomial time algorithms for any NP-complete problems. "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?" That doesn't seem materially different than having to pick key lengths. There is some amount of work you expect to be beyond what your opponents could theoretically muster. Pad a bit for safety. "So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not." We're using NP as a proxy for "provably different lower bound on checking versus finding". It's not a bad proxy, but having an actual proof of lower bound should be even better whether or not it is exponential, provided there's a sufficient gap to make realistic key sizes useful. [1] Edited to add: As pointed out to me below, there are plenty of examples of O(n^k) with arbitrarily high k. This certainly undermines my speculation about human capabilities. At the same time, it means it does happen in practice.

spooningtamarin 11y ago
There are plenty of algorithms with n^k where k>4, just not useful ones. Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that seem very real, and solutions (algorithms) definitely show very lovely interaction of several different areas of research, problem solving skills at its finest. http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...
- dllthomas 11y ago
  Thanks! That weakens my speculation about human capabilities, though the fact that it deserves calling out as "problem solving skills at its finest" seems to leave me some wiggle room ;) To be honest, I'm not sure how to quantify the relative populations of higher-exponent and lower-exponent found algorithms, and if there is a skew some of that might well be due to the decreased attention to the space of higher exponent algorithms due to lower expected usefulness...

Dylan16807 11y ago

> Is n^100 secure, but n^99 not? Is 128 bits secure, but 127 not? At some point you have to arbitrarily pick a threat model. Pick a budget, a number of decades of Moore's law, and how big of an extra buffer you want. Then pray there are no gaping algorithmic flaws. This is the same whether you're looking at O(n^7) or O(2^n). The closer brute forcing gets to normal use, the worse your engineering tradeoffs have to get. But there's no magic number where crypto fails. It just slowly becomes less practical in more situations. If brute force time is at least the cube of encryption time, you barely have to worry about it being P.

baddox 11y ago

> 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? That doesn't sound right. After all, there's already an arbitrarily smooth continuum between polynomial-time and exponential-time algorithms. See quasipolymomial or sub-exponential algorithms.