[mostyfriedman]

Hey Everyone,

So today a coworker gave me this link of a proof that P != NP by a researcher working at hp. I haven't gone through the paper yet since i am at work, but some people think that this is it, this is the proof that we have been waiting for. Anyway here it is in case you wanna check it out.

P != NP

[KYA]

I saw this on the news feed the other day. Thanks for the document link!


Featured.

[reinekec]

mostyfriedman, on 09 August 2010 - 04:30 AM, said:

Hey Everyone,

So today a coworker gave me this link of a proof that P != NP by a researcher working at hp. I haven't gone through the paper yet since i am at work, but some people think that this is it, this is the proof that we have been waiting for. Anyway here it is in case you wanna check it out.

P != NP

I took a class in college called Formal logic and Computation Theory (A.K.A Finite Automata and Formal Languages). P != NP was heavily discussed in the course. Was very interesting.

[mostyfriedman]

I also took a theory of computation course, was my hardest yet favorite course.

[Sergio Tapia]

That paper is going to be so under the microscope! Let's see how it turns out. The paper took approx. five years for him to write (read about it on Reddit a yesterday) so imagine how long it will take to verify among the top minds in the world.

I hope it's proof though!

[mostyfriedman]

Sergio Tapia, on 10 August 2010 - 05:25 PM, said:

I hope it's proof though!

I hope its not, imagine how much power we'd have if someone finds an algorithm that solves an NP problem in time P.

[Nikitin]

mostyfriedman, on 10 August 2010 - 07:27 AM, said:

Sergio Tapia, on 10 August 2010 - 05:25 PM, said:

I hope it's proof though!

I hope its not, imagine how much power we'd have if someone finds an algorithm that solves an NP problem in time P.

Like factoring, which would make obsolete the whole foundation of cryptography? Good guys won't be the only ones with that power. Whatever it might be, it's mathematics, it is what it should be.

[mostyfriedman]

so what? passwords will be easily broken, maybe we can think of better ways to protect data than a password, i dunno just use your creativity.

[Nikitin]

Passwords are passwords, I'm talking about encryption of secure data (think of public keys, SSL, DES, etc). Pretty much everything from banking industry to national defense would be compromised in one way or another.

True, we might find other ways of securing data, I'm not going to argue about that. I simply wanted to point out that there are negatives that would come along as well. I myself don't really have an opinion on this matter - because it's mathematics, it's truth is absolute. Wanting it turn out another way is wanting mathematics to not work.

[Scorpiion]

Interesting... Need to read this later!

Source of Vinay Deolalikar papers at HP:
http://www.hpl.hp.co...lalikar/Papers/

This post has been edited by Scorpiion: 10 August 2010 - 10:33 PM

[Vestah]

It looks pretty cool. I really look forward to the details analysis it will get.

Here is a page which show other attempts at solving P = NP: http://www.win.tue.n...P-versus-NP.htm

[SwiftStriker00]

I am actually taking a CS Theory class. and this proof pretty much came out when we started talking about P and NP. My prof naturally was vary interested in it too seeing how he doesn't believe this proof will be done for another few decades or at all. However he says that there are already a handful of flaws that other people have found, so he doesn't believe that it will be conclusive, but still quite interesting.

[guahguahmonster]

Even more fun? Scott Aaronson essentially puts $200,000 against the proof being correct.

http://scottaaronson.com/blog/?p=456