HP labs researcher thinks he might have proof of P≠NP, has another Millennium problem been solved?
By Laura June 
posted August 10th 2010 12:21PM
posted August 10th 2010 12:21PM
posted August 10th 2010 12:21PM
A look back on popular stories from today in a specific year.
Now that we've thrown 'em off the trail, use the form below to get in touch with the people at Engadget. Please fill in all of the required fields because they're required.
Shit, he beat me to it...
Although i personally think that eventually P==NP
@User42
when i first read it i thought it was an article about UPNP, how wrong i was..
@User42
You personally think this? How so, seeing how there is nothing in the world that proves it to be true. After all you would only need to solve one NP-complete problem to prove P=NP.
@KillaChaos It's a matter of looking at the problem with a different language (or a set of tools). I believe the problem is a "problem" because it cannot be contextualized with any present language. However if someone were to come up with a language that was simply derived from logic and not from Latin then we might actually be able to tackle this "problem"
@User42
So we are indeed talking about mathematics here then?
Or am I missing your joke, User42?
Or... err..
@astrath yes we are talking about math, for example, in math not all proofs have been proven and if you think they have, you have much to learn.
@User42
No, you're an idiot. In math there are sets of axioms that are taken to be true without proof (and are not considered proofs) with the assumption that they are internally consistent. Starting with those axioms every mathematical "proof" is indeed "proven". There is a formal symbolic language statement (or an equivalent statement of a non-formal symbolic language statement) with a set of acceptable derivations of every theorem starting from the axioms (usually the ZFC axioms). Anything that has not been thoroughly "proven" (follows from the ZFC axioms using theorems that were proven or allowed substitution rules in the formal symbolic language) is not a "proof" nor a theorem.
If something is suspected to be true/false, it is called a conjecture, and sometimes physicists or other users of math who are not mathematicians will assume something to be true because it seems to work and for their purposes it does. However in mathematics every "proof" is "proven".
@MrDiSante
ooh sweet pilllow talk
@MrDiSante First off, I never called anyone an idiot, so chill.
And second, I apologize that I wasn't clear with what I meant to say, it should have been: that there EXISTS proofs that have not yet been discovered/proven. If you think that all proofs have been proven, then you're dead wrong. There are proofs and conjectures (or whatever you want to call them) that haven't even surfaced mankind's minds. For example, this would be same argument when the world was thought to have been flat or at the center of the solar system/universe. Some proofs get unleashed because of a new way of thinking and my original argument was that this proof won't be proven until we do that.
@MrDiSante
@User42
That's the problem with discussing stuff online. One guy (MrDiSante) obviously knows what he's talking about and the other (User42) is well into his 3rd joint. You can't expect anything meaningful from this.
It really doesn't make sense to say a proof has been proven. By its very nature a proof is...well.. a proof and hence proven. I think you mean there are truths that haven been proven, which is pretty damn obvious to everyone with even a lemon slice of a brain.
@LeJay
Yes, user42 indeed seems to be smoking something.
@LeJay @whiskers prove it :P
@User42
I hold that truth to be self evident.
@LeJay hilarious but false.
@User42
im pretty sure that 8===>
@User42 : P≠NP, depends on how dirty the bathroom looks. :)
@MrDiSante
"In math there are sets of axioms that are taken to be true without proof (and are not considered proofs) with the assumption that they are internally consistent."
Why not just make P≠NP an axiom then? No proof required. :-)
@User42 A proof is proven by definition of the word. You use the wrong vocabulary and it's no fault of anyone but yourself.
And "Shit, he beat me to it... ", I hope you are not serious?
@HKCally
Because the axioms should be independent of each other, or at the very least internally consistent. For instance, in the ZFC (Zermelo-Fraenkel-Choice, the most widely accepted) axiom set, there was wide dispute over whether the Axiom of Choice should be included and whether it lead to contradictory results.
If the P=NP problem is not independent of ZFC, and we assume the wrong result as the axiom that will lead to major problems. For instance, using proof by contradiction you will be able to prove any result (regardless of whether it is "right" or "wrong") such as 1=2.
@MrDiSante Just wanted to thank you for your responses. This topic was pretty well beyond my areas of knowledge, but you've explained things rather well.
If I didn't know any better, I'd say that the existence User42 and MrDiSante just provided an informal proof that P!=NP
hahahahaha
Yes....errr....No...errr...DOH !
Fucking magnets, How do they work?
@nickyP
I know, and here's me, still wiping my ass with a dock leaf
Here is my submission:
Yes. Yes? Yes.
@Barguast
You nailed it.
@sajkhoe
Approved. Please pick up your million dollars now.
or...
No. No? Yes. Yes? No. No? Yes. Yes? No. No? Yes. Yes? No. YES & NO NO YES YES YESO IU#BNWIONQDFOW#NIDF"NIWQ"D
QWD{P
My head hurts, already.
This is how I know I'm American.
@tageier
Have another Molson, you Canadian American!
@Funke Tobias Dr
Pretty sure Molson is American
@Matt314
I'm pretty sure you are incorrect.
@Matt314
Molson is purely Canadian
@kapanak
Clearly Canadian.
Yes, and yes?
Wow quick million for sure
I figured it out first, he stole my research
he P versus NP problem is a major unsolved problem in theoretical computer science and mathematical logic. Informally, it asks whether every problem with a yes-or-no answer whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. It is considered by many theoretical computer scientists to be the most important problem in the field.[2] The Clay Mathematics Institute, which is dedicated to increasing and disseminating mathematical knowledge, has included it in its list of Millennium Prize Problems; anyone who provides a satisfactory solution to the problem may be entitled to a USD $1,000,000 prize.[3][4]
In essence, the question P = NP? asks:
Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"?
The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice. The general class of questions for which some algorithm can provide a yes-or-no answer in polynomial time is called "class P" or just "P".
For some questions, there is no known way to find an answer quickly, but if one is provided with information showing that the answer is "yes" (known as a certificate), it may be possible to verify the certificate quickly. The class of yes-or-no questions for which a certificate can be verified in polynomial time is called NP.
Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer is yes, because {−2, −3, −10, 15} add up to zero, and this answer can be quickly verified with three additions. However, finding such a subset in the first place could take more time. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.
An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
The restriction to yes/no problems is unimportant; when more complicated answers are allowed the extension to function problems becomes FP = FNP, which has been proven to be equivalent to P = NP.[5]
@rmbrown09
i wonder if anyone is as impressed by your comment as much as you are.
@profgaylord It's a copy/paste anyway. Not sure why he didn't just paste the link.
@rmbrown09
He's just jealous. I came looking here for a better explanation and found it thanks to you.
@profgaylord
I actually am, Stop being unappreciative.
Read and Learn
@profgaylord Only the person that created that Wiki he copied.
@rmbrown09
well whata the time requirement of "quickly"?
Cant this all be solved with an statement from DOS?
:Start
IF "yes" then goto EOF
IF "no" then GOTO Start
lol
@rmbrown09 http://en.wikipedia.org/wiki/P%3Dnp
@triptych
And? It's informative and not everyone wants to click on a link; it was well suited to be copy-pasta'd right here in the comments. Thanks for the info, even though I didn't understand a few bits I now get the gist of it.
@rmbrown09 Here is a link to the actual paper:
http://www.scribd.com/doc/35539144/pnp12pt
@rmbrown09
Good post, even if it is C+P'd.
It's alot better than engadget's explanation.
@mixit here is a quote from the paper that proves this to be true
"In order to apply this picture in full generality to allLFP computations, we use the simultaneous induction lemma to push all simultaneous inductions into nested ones, and then employ the transitivity theorem to encode nested fixed points as sections of a single relation of higher arity.Finally, we either do the extra bookkeeping to work with relations of higher arity, or work in a larger structure where the relation of higher arity is monadic (namely, structures of k-types of the original structure).Either of these cases presents only a polyno- mially larger overhead, and does not hamper our proof scheme.Building the machinery that can precisely map all these cases to the picture of factorization"
@Double J
my bad. i apologize. i hadn't recognized that rather than trying to impress people with your knowledge of the subject, you were simply plagiarizing (using the words of another without attribution) a wiki article (i wouldn't have made that mistake if you had acknowledged the source of your material).
@profgaylord No problem, you are the only one here to do so, everyone else was intelligent enough to realize. All this does is point out you were the least intuitive of every commenter.
Buck up