Let me put this another way, because I think it helpfully illustrates one of the quirks of the complexity class P (and indeed, of any reasonable language of total functions), and is just amusing-sounding to boot: The problem “Given a polynomial-time program P [even with the polynomial explicitly specified] and input X, determine P(X)” cannot be solved in polynomial time. In other (slightly facetious) words, there’s no fast way to carry out fast computation.
P!NP’n ain’t easy.
THEY CANCELED NUMB3RS?!?!?! :eek:
Oh well…was a bit formulaic anyway. Crime happens, Don consults Charlie, Charlie has a theory, brother drama, theory wrong, Charlie modifies theory, police showdown, brother drama resolved, beers with Judd Hirsch.
Math drama formulaic, derivative. Film at 11.
The notion of determinism is somewhat confusing, and given that there’s a characterization of NP in terms of solution verification (i.e., one question interactive proofs) which is much easier to understand, that’s the approach I prefer to take.
That was just dreadful.
I wish I’d thought of it.
Worth noting that one of the fascinations P and NP problems have for computer scientists is that if you can solve one problem in a class, you can typically transform other problems into that problem and use the same solution.
So if P = NP, that would be a big deal, since the proof that they were equal would probably help us towards faster solutions for the NP problems. Knowing that P != NP takes away that hope, but that’s reassuring for security people who want the hard problems to stay hard.
Fascinating stuff, even if it just confirms what was already suspected.
So after hearing the news, I was brushing up on the topic at Wikipedia (and other sources), where I came across this tidbit:
Is P equal to NP?
In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and so impossible to prove or disprove.
(Bolding mine.)
I find this last position surprising, and had no idea it was a serious consideration. I would have thought you could say: “P != NP is possibly true but unproveable”, but not “P != NP can be true or false as you wish; pick which one you like (and see what follows).”
Am I misreading what’s being said? Or maybe those 8 people are just oddballs?
Of course the whole point is moot if Deolalikar’s proof holds. No more need to take bets then. Not that I think mathematical truths are contingent on opinion polls.
Yes. When they say that they think it’s independent of the axioms of the system, they mean what you said earlier–that it is either true or false, but impossible to determine which.
Do keep in mind that provability is always relative to a particular set of rules, and there’s no such thing as being objectively unprovable, only unprovable from a particular set of rules. For P vs. NP to have been independent from the particular game ZF, say, would’ve been no more intrinsically fantastic a concept than for a bishop in chess to be unable to ever reach any of the squares along a certain diagonal. Why should it have been able to? The rules of the game are what they are; they’re not going to magically ensure everything goes one way or another.
I have more spiel to give on the matter of “independent of the currently accepted axioms and so impossible to prove or disprove”, but I’m too lazy right now… Besides, I’m sure at least some of you have heard at least some of it before and could give it yourself.
Just to follow up on this, the “halting problem” (determine the result of running a specified program on a specified input) is known to be outside NP, too, so the answer to the P=NP? question has no real bearing on it. There are a sizeable number of these problem classes, P & NP are the “inner rings,” so to speak, of a large Venn Diagram of problem and problem classes, including some that are known to be inherently unsolvable by any computational (important to include that word) means whatsoever.
(These latter include the “This statement is a lie” variety, as well as more subtle ones.)
Although quite a lot of the uncomputable problems turn out to be uncomputable specifically because the ones of the “This statement is a lie” variety are reducible to them (not just the Halting Problem, but also similar constructions of lesser Turing degree). But, out of curiosity, which kinds of problems are you referring to by “more subtle ones”?
My first reaction is Wow! Of course, I will wait and see. It is, incidentally, one of the Clay million dollar problems.
Now how important it is will likely depend on whatever new methods were invented to deal with it. The proof of the four-color theorem was very clever (at least Heesch’s ideas were, but he didn’t have a computer). Haken and Appel both contributed many new improvements on Heesch and some people have since, but, AFAIK, nothing else has ever come of the theorem or its proof. The proof of the Fermat conjecture is entirely different. One could argue that the whole of abstract algebra was invented to try to solve the FLT. That’s an exaggeration (Galois also contributed a lot), but there is a kernel of truth to it. Wiles’s proof also led eventually to the proof of the Taniyama conjecture, an important conjecture in algebraic geometry. So the attempts on the FLT led to many advances in math. The same is true of the Poincaré conjecture (another Clay prize, although the money was refused).
Now, no one believed that P = NP, but it was an embarrassment that it is was still open. Incidentally, it leaves open the question of whether RSA encryption is safe, because prime factorization is not (or anyway not known to be) NP complete. That is it could turn out to be P without implying anything about other NP problems.
But it is always interesting when a conjecture is settled.
The holy grail of current mathematics remains the Riemann hypothesis.
For those following the story, here’s an interesting new post from comp-sci professors Ken Regan and Dick Lipton, mentioning some possible problems:
I love this explanation. Thanks Chronos.
one more request:
You mentioned, that if it was shown that P = NP zombies would eat our brains… well, you mentioned encryption would go out the window. I understood that, but what are other examples of things what would change if P = NP?
And one final question though it’s selfish and tangential to the OP and for that I apologize: What books do you guys recommend for a layman to read about some of the more important, notable or otherwise interesting mathematical problems both solved and left unsolved?
Well, one thing P = NP would let you do is quickly answer the question “Is there a proof of so-and-so in formal system such-and-such of size less than so-and-such?”. In this sense, Goedel claimed to von Neumann, mathematics would effectively become automated if P = NP; not in that it would become possible to quickly decide whether a statement is or is not provable (this is not in fact generally computable at all), but in that it would become possibly to quickly decide whether a statement does or does not have a proof within such a size as that someone might ever feasibly write it out. So, on that point of view, it would end mathematics as we know it.
(All this on the usual identification of “quickly” with “polynomial-time”)
(And, I should say, as part of this it would also be possible to quickly generate such a proof whenever one exists)
Take a look at Wikipedia’s very incomplete list of NP-complete problems. Everything on there except for the ones in the section on algebra and number theory is a problem that somebody wants to solve in the real world (and even the others might have practical consequences, although I’m not familiar with most of them).
It’s worth noting that the problems which would be placed in P if P = NP even go well beyond merely (what we currently know to be in) NP; if P = NP, the entirety of PH (the polynomial hierarchy) will collapse into P as well. For example, the problem of determining whether two given expressions built out of multiple variables, constants, addition, and multiplication are always equal is not known to lie in NP; however, nonetheless, if P = NP, then this problem is polynomial time as well (essentially by two “iterations” of the reduction from NP to P).
Whoops, sorry, I gave that problem stupidly wrong; it’s clearly in NP (well, co-NP, and not known to be in NP, but that’s effectively the same; what threw me is that is in BPP). Still, the point of the post aside from the example remains true.