Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by ramchip on Monday April 12, 2010 @10:02AM
(#1259119)
I don't think proving N = NP would necessarily give us an easy way to transform any NP problem into a P one. It could be a nonconstructive proof. You would know that a given encryption could possibly be cracked, but not how.
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by g__ on Monday April 12, 2010 @01:32PM
(#1259789)
Under assumption P=NP, a polynomial algorithm is already known (!): http://en.wikipedia.org/wiki/P_%3D_NP_problem#Polynomial-tim...
The problem is: will humanity find a feasible algorithm?
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by tetha on Monday April 12, 2010 @01:37AM
(#1258499)
You either had to be very, very delicate or you had to spread the knowledge to too many people before they can react properly.
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by arethuza on Monday April 12, 2010 @06:04AM
(#1258806)
Someone announcing P=NP in a non-delicate way is part of Charlie Stross's story "Antibodies".
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by rlpb on Monday April 12, 2010 @06:50AM
(#1258853)
Assuming that it would be a very complex proof, it might take a while for practical applications to be able to catch up.
My favorite conspiracy theory is that P = NP and the NSA is covering it up.