Some argue that the question is not as important as it is widely believed to be (see Sariel Har-Peled's opinion in the poll) - many NP hard problems have practical approximations, many P problems are prohibitively costly to solve.
> many NP hard problems have practical approximations, many P problems are prohibitively costly to solve.
I don't know if there is more to Sariel Har-Peleed's piece than the one paragraph in the poll, but as of today, most P problems used in practice actually have a very good running time O(n^3) or O(n^4). I don't know if there are too many problems that are in P but only "theoretically".
Also, even though P=?NP might not have very practical ramifications, if one believes in the notion of asymptotic complexity, it raises fundamental philosophical questions -- is judging creativity as easy as being creative.
I see that piece mentioned a lot, but I don't think it's really in keeping with the existing philosophy or research on computational creativity. There's a lot of disagreement of course, but a vague consensus is that the formalization problem is harder than the computational complexity problem: computers composing novel, good symphonies is not mainly bottlenecked by computational complexity, but because we don't know how to write a program to do it (in any running time).
Put differently, why is symphony composition harder than SAT? You can download programs right now to solve huge classes of SAT, but not to compose huge classes of symphonies (David Cope's interesting work notwithstanding).
That's an interesting read! I think his point is that NP-completeness does not give you an intuition about the hardness of automating creativity. That point is granted. However, if P were equal to NP, then it would imply that we can write algorithms that can automate creativity (Levin's algorithm is an algorithm to solve all NP-complete problems in polynomial time, if P=NP); which will raise an interesting philosophical debate all on its own.
I don't know if there are too many problems that are in P but only "theoretically".
Actually there is a known class of problems that are in P, but only "theoretically"! But for very different reasons than what you are thining of.
See http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theor... for a theorem that implies that certain types of graphs are characterized by a finite set of forbidden graphs that cannot be embedded in any form. (I'm being vague about "in any form" here, what I mean is that you can't do things like subdivide an edge and put a point in the middle then say, "Here! I changed it." More formally the forbidden subgraph can't be a minor of the main graph. See http://en.wikipedia.org/wiki/Minor_%28graph_theory%29 for an explanation of what a minor is.) For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.) Any graph that does not contain these anywhere is planar.
It turns out a finite forbidden set of minors can always be tested in polynomial time. Therefore an class of graphs that meets the conditions for the Robertson-Seymour theorem has a polynomial time test.
Here is the catch. For many classes of graph we can prove that this polynomial time test exists. But we don't actually know what it is. Finding it requires enumerating the finite set of forbidden minors. But we have no way to figure out what they are. For graphs that can be embedded in the plane we know that there are just two. The projective plane turns out to have 138. As of 2004 I know that were nearly 240,000 known for the torus, and this list was not believed to be complete. According to http://www.cs.uvic.ca/~ruskey/Theses/WoodcockMScThesis.pdf there were theoretical algorithms that were O(n) and O(n^3), but nobody had ever implemented them and it was suspected that they would be too slow to use in practice. Moving on, consider the set of graphs that can be embedded in 3D without any knots. To the best of my knowledge nobody even has an exponential algorithm for that - yet we know that the problem must be in P.
So there you are. A whole family of problems, all of whom are known theoretically to have solutions in P, but for most of them we have no way to find said solutions, and even if we did find them they would likely be too slow to use in practice.
> For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.)
Huh. I know this intuitively from doing those "try to connect the three houses to the three respurces without crossing any lines" kind of puzzles when I was younger—but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem. My (puny) knowledge of topology has been made slightly more concrete. :)
but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem.
Sorry, but the proof of the four-color theorem is much, much more difficult than the proof of this result. (Which is called Kuratowski's theorem and was proved in 1930.)
Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical.
I agree about the philosophical questions, but don't they also rely on the practical ramifications of the question?
"is judging creativity as easy as being creative"
What if P=NP, and for some problem there is a practical polynomial algorithm for checking a solution but only an impractical polynomial algorithm for finding a solution? What I mean is that the philosophical ramifications also depend on the assumption that polynomial~easy.
>n^3 or n^4 might already be considered impractical in many situation
You can always make these arguments for large enough N and short enough time constraints. It is an argument that as an engineer I sympathize with, but as a computer scientist I cannot endorse. The question of P=?NP is a mathematical and philosophical question. The problem of O(N) algorithms being too slow for situation X is an engineering question.
So while I recognize and even sympathize with you point, I do not think it detracts from the fundamental importance of the question at stake.
True, there is the engineering aspect, but I didn't mean that, I was talking about the same fundamental philosophical question you were.
That is, "are there problems for which we can easily verify a solution but not easily find one". P=?NP is only relevant to this philosophical question, if we accept that "polynomial" is synonymous with "easy". That is a widely accepted statement, but not entirely obvious. As it was said in the linked poll, even a polynomial running time could hide contants so large, that it is prohibitively large not just today but anytime in the future until the universe collapses upon itself. On the other hand there can be NP-hard problems for which we can find arbitrarily close approximations in reasonable time. The question is how well are our theoretical efforts capturing this intuition.
> Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical.
Ah, so you now you can see how pathetic our understanding of computational complexity is when we consider algorithms that are linear sometimes impractical but we cannot show we can do better than an exponentially worse off bound for SAT instances (Today's best SAT algorithms run in time 2^O(n)).
Even accepting the leaps, the false underlying assumption is that if P = NP there must be a proof. Goedel's Incompleteness Theorem's key result is that within any logical system there are truths that cannot be proven.
It follows that we may never be able to prove that P = NP or P ≠ NP, even though one of the two must be true.
Actually, there are problems that are neither provably true/false, nor actually true/false. In fact I think a standard counting argument shows that 99.9999...% are in that category.
Yes but incompleteness refers to things that are true but can't be proven to be true.
I think you're referring to the idea of prospective axioms which can be proven to be independent of existing axioms (notably the axiom of choice). This is another thing altogether.
In the end, knowing enough about something to reduce it to axioms is only the start and not the end of understanding. P = NP wouldn't suddenly trivialize the problems so much as indicate that a polynomial time solution exists somewhere.
Some argue that the question is not as important as it is widely believed to be (see Sariel Har-Peled's opinion in the poll) - many NP hard problems have practical approximations, many P problems are prohibitively costly to solve.