Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by sswam on Sunday April 11, 2010 @09:00PM
(#1258068)
or perhaps he can break RSA in polynomial time or something like that
[ Parent
| on HN ]
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by noamsml on Sunday April 11, 2010 @10:15PM
(#1258198)
Pretty sure that's the same thing as proving P=NP.
Re:Donald Knuth making an Earthshaking Announcement June 30 ...
by Locke1689 on Sunday April 11, 2010 @11:27PM
(#1258315)
No it's not. The factoring problem/RSA problem have never been proven to be NP-complete. Shor's algorithm shows that it's NP, but not NP-complete (or hard). I think it's also in co-NP.
[deleted]