News for hackers. Stuff that matters.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by baddox on Sunday April 11, 2010 @04:42PM (#1257555)
I'm hoping he's discovered if P=NP.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by kloncks on Sunday April 11, 2010 @04:46PM (#1257562)
That will indue live up to the "earth shattering" promise.

I think it might be one of the few, if not the only thing, that would live up to that.

Re:Donald Knuth making an Earthshaking Announcement June 30 ... by baddox on Sunday April 11, 2010 @11:01PM (#1258273)
From the little I know about Knuth, while he is a bit of a joker, he doesn't seem like the type to make an announcement to hype people up. That either leads me to believe this will actually be something huge, or it's just a joke of some sort.
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
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]
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by PG-13 on Monday April 12, 2010 @12:37AM (#1258414)
Yeah.... but like he said, RSA being in P does not imply that P=NP because RSA has not be shown (and isn't believed) to be NP-complete. If P=NP, then RSA would of course be in P.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by sswam on Sunday April 11, 2010 @09:00PM (#1258071)
or maybe he's finished another book!!!! :)
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by philwelch on Monday April 12, 2010 @01:13AM (#1258464)
Something tells me that if P = NP, they would have to be...delicate about announcing it, given the implications for cryptography.

My favorite conspiracy theory is that P = NP and the NSA is covering it up.

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.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by dmoney on Monday April 12, 2010 @08:17AM (#1258956)
How would you go about announcing this delicately? For a security vulnerability, one would tell the vendor first. So, tell all cryptography vendors before everybody else?
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by rlpb on Monday April 12, 2010 @01:17PM (#1259746)
This reminds me of the buggy-whip analogy. Cryptography vendors will be screwed. Security vendors might have a chance.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by elblanco on Sunday April 11, 2010 @07:59PM (#1257980)
That's exactly what I thought the moment I saw this. The other options are a working quantum computer or he's retiring.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by BoppreH on Sunday April 11, 2010 @11:18PM (#1258304)
I would start thinking badly of him if he referred to his retirement announcement as "earthshaking".
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by faragon on Sunday April 11, 2010 @05:34PM (#1257654)
Why not? In addition, he could demostrate that any given NP problem can be solved in O(N^2) time complexity.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by jrp on Sunday April 11, 2010 @07:56PM (#1257974)
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by tjr on Sunday April 11, 2010 @08:46PM (#1258041)
As if that could stop Knuth...
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by faragon on Monday April 12, 2010 @02:07AM (#1258537)
But what if you:

1) Create a list of pairs for the N nodes, N^2/2 elements: O(N^2). This point complexity could be ignored, as an initialization phase, as precomputed data for next step. In addition, many lists of hamiltonian subpaths could be added for trading memory for time complexity (not big deal, just linear speedup).

2) Dynamic-size (hamiltonian path subset) algebraic mergesort (avoiding evaluation, in order to avoid O(N!)): O(NlogN), or maybe O(N^2), or O(N^2logN)

That could give you time complexity between O(N^2) and O(N^2logN). I tried something for the point (2), but obviously I had no success on compensating the combinatorial explosion with simplification/remapping. Possible or not, it is neverending and cheap fun.

Re:Donald Knuth making an Earthshaking Announcement June 30 ... by eru on Sunday April 11, 2010 @07:12PM (#1257883)
I guess that'll be impossible.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by nopassrecover on Monday April 12, 2010 @10:30AM (#1259183)
I doubt he'd wait until the TeX speaking role to announce that.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by Dellort on Sunday April 11, 2010 @05:57PM (#1257718)
That is obviously wrong as there's an N in there. CS professors will tell you the same.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by TimothyFitz on Sunday April 11, 2010 @06:47PM (#1257837)
The way my prof told it: "I'm really not sure why people keep asking if P=NP. Of course it does, when N=1."
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by jonp on Monday April 12, 2010 @06:57AM (#1258864)
Or P=0.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by tjarratt on Sunday April 11, 2010 @09:05PM (#1258076)
aha
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by orp on Sunday April 11, 2010 @06:35PM (#1257806)
Sarcasm?
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by Dellort on Sunday April 11, 2010 @06:50PM (#1257845)
Use your professors. There are no stupid questions only stupid answers. I am sure they will be glad that you ask, assuming you are a CS student.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by jacobolus on Sunday April 11, 2010 @09:52PM (#1258154)
Are you trying to make some kind of joke? NP = “nondeterministic polynomial time”, and it is a complexity class of computation problems.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by richcollins on Sunday April 11, 2010 @06:20PM (#1257772)
Dammit you beat me to it :-)