6 ms·

How does "polynomial" imply "practically tractable"? If P = NP, the exponent may well something like x^100 or x^(# of atoms in the Universe)

• stonogo 10y ago
  Because 'polynomial time' is a long-standing term in time complexity theory defined to imply tractability.
• CJefferson 10y ago
  I agree. I've produced x^8 algorithms, which are already completely useless for all practical applications. If a proof has 10,000 statements, we already couldnt generate it with an x^8 algorithm.
• bhrgunatha 10y ago
  Yes, this always confuses me. Why the constants are swept under teh carpet for real world, practical applications. From the same article. "It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice." Given the long standing nature of the problem, my guess is that some new techniques or insights will be required to solve it one way or the other. Those may well give clues to solving NP/NP-Complete problems efficiently. Until someone actually does it though it's still just speculation.
  • Smaug123 10y ago
    Aaronson specifically addresses this in section 1.2.1, on page 6.
    • bhrgunatha 10y ago
      To be clear I'm not talking about how useful asymptotic analysis and big O notation are in general, I'm talking specifically about the case if we eventually do prove P = NP. Internet lore and popular media then assume that immediately for example all encryption will be trivially broken. Mathematically it may be true because then all NP problems would be known to be polynomial, but there's still the issue of the practical steps involved factorising a huge number which may have enormous constants or very large exponents. Or if it turns out we can reduce it to some other known polynomial problem, there's still the actual transformation which itself may be polynomial with large constants or exponents.
      • Beltiras 10y ago
        If P=NP is proven than that makes factorization an easy problem (and included in the proof) which would make many algorithms for encryption "trivially broken".
        • lomnakkus 10y ago
          Right, but it's worth mentioning that factorization itself is not known to be NP-hard (and it's suspected not to be, by most, I think). Also, as others have pointed out, the constants involved in any "generic" algorithm for solving any NP problem in Polynomial type may be astronomical, so even if it turns out that P=NP, then it may not ever be feasible to actually such any algorithm for anything practical.
      • smitherfield 10y ago
        If I'm not mistaken, isn't it also the case that factorization hasn't been proven to be in NP?
        • teraflop 10y ago
          That's not quite correct. Factorization is definitely in NP, because verifying whether a number has a particular factor is easy. Maybe you meant that factorization hasn't been proven to be NP-complete, which is true. In fact it would be very surprising if it was NP-complete, because that would imply other surprising things (e.g. NP = co-NP).
  • smallnamespace 10y ago
    One answer is because in practice, we very rarely see large constants anywhere. While theoretically x^1000 algorithms exist, it's hard to actually find a reasonable example of one. Ditto for e^1.00000001. Of course, why this might be the case remains to be investigated.
    • taeric 10y ago
      Do we rarely see large constants? Or are they just not on problems where precision and "absolute best answer" matter? As an example, an algorithm to find the optimal solution to a Rubik's cube would actually be very difficult to do. However, finding a solution in a short enough time frame is quite easy. This is more true the larger of a cube you try and solve. Contrast this with problems such as encryption, where we have specifically made problems where there is not a "best answer", but rather there is only a single answer that matters.
      • smallnamespace 10y ago
        I think you're proving my point here -- finding the optimal solution for a Rubik's cube is probably at least PSPACE-Hard, which is probably exponential. So complexity theory is confirming your intuition, which is that 'optimization type problems' are hard.
        • dom0 10y ago
          Even the basic rucksack optimization problem is NP-hard. I'd dare say that a huge class of optimization problems maps very naturally to this particular one, https://news.ycombinator.com/item?id=13316776 https://news.ycombinator.com/item?id=13316776 for starters.
          • taeric 10y ago
            Ok, so optimization problems are potentially bounded with smaller coefficients than we would think. What about sequencing life? Supposedly we share a lot at the genomic level with animals we are vastly different from. Could a large degree of the polynomial that is life explain that divergence?
• Ar-Curunir 10y ago
  The linked survey comments on this; whenever we've been able to put a problem in P, we've almost always been to bring down the exponent to practical sizes.
  • VLM 10y ago
    The classic low hanging fruit problem. Whenever we've pumped an oil well dry, we've almost always found another easy to pump well, therefore all oil wells are easy to exploit and we'll never run out of oil. There are other analogies with the ease of catching wild passenger pigeons and bison.
    • cwillu 10y ago
      In point of fact, the survey gives a bit more detail than what the parent implied.
• jonathanstrange 10y ago
  That's what Knuth suspects, P=NP, but essentially impractical and not tractable.
• nine_k 10y ago
  There is a fair chance that the exponent will be of tractable magnitude for certain practically interesting classes of problems.