How does "polynomial" imply "practically tractable"?
If P = NP, the exponent may well something like x^100 or x^(# of atoms in the Universe)
If P = NP, the exponent may well something like x^100 or x^(# of atoms in the Universe)
"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.
Of course, why this might be the case remains to be investigated.
The best approximation algorithm (it's NP-hard) runs in time O(n^(10^100)):
https://arxiv.org/pdf/1205.0458v2.pdf
For more examples see here http://cstheory.stackexchange.com/questions/6660/polynomial-...
Do you have examples of large-constant algorithms in P that are not approximations of NP-Hard problems?
One example are all the consequences of the Robertson-Seymour theorem which (non-constructively) asserts that a large number of graph problems "is in P". For instance, we know that testing whether a graph can be embedded in the torus is in P, but the algorithm in question is completely infeasible.
I would expect a positive answer to P = NP to be completely useless in practice. A negative answer would similarly be rather unexiting by itself. What would be exiting are the tools for getting this answer...
One of those is that according to classical mathematics there are concrete problems with polynomial time algorithms that there is no way of producing, and if produced, there is no way of verifying. (Literally no way of verifying, pick an axiom system and there are problems for which the question of whether there is one more forbidden minor is undecidable in said axiom system.)
If you doubt that such algorithms have any real existence, you might be a closet constructivist...
That's basically Donald Knuth's position. http://www.informit.com/articles/article.aspx?p=2213858
This can lead to large constants, but doesn't have to. It depends on the value of the fixed parameter.
That finite list can be extremely long indeed. And in some cases, there is no way of finding or verifying the full list.
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.
So complexity theory is confirming your intuition, which is that 'optimization type problems' are hard.
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?
I am assuming you are pushing the same angle as the other poster. That is, most optimization problems are actually not "large constants" in the exponents. So, since most of what developers think of as "hard" are almost all classical NP problems, maybe it makes sense to look at other things we don't typically think of as computational.
Could just be nonsensical, though. I fully accept that.
Edit: I meant "small" coefficients above. Apologies.
NP: probably O(e^kn), k>1, where k close to 1 makes it 'fast', but still exponential
The objection is that k can be big for some polynomial algorithms but small (near 1) for other exponential ones, so we can have 'slow' polynomial algorithms and 'fast' exponential ones.
But in practice, k is usually small for polynomial algorithms and not close to 1 for exponential ones so simply knowing whether an algorithm is exponential or polynomial tells you something.
The 'hard' problems you gave me all (probably) fall into the exponential runtime class, whereas the easier ones (like finding any solution to a Rubiks) fall into the polynomial runtime. So your intuition of 'hard' vs. 'easy' matches complexity theory's evaluation, even though theoretically there could be really slow 'easy' problems and really fast 'hard' ones.
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.
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).
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.
If a proof has 10,000 statements, we already couldnt generate it with an x^8 algorithm.