Donald Knuth making an Earthshaking Announcement June 30 in San Francisco | Hacker News Reader

Donald Knuth making an Earthshaking Announcement June 30 in San Francisco

www-cs-faculty.stanford.edu

167 pointsjackfoxy86 comments

I'm surprised that no-one has suggested the obvious: that The Art Of Computer Programming Vol. 4 - Combinatorial Algorithms is complete.

But that's no fun, so I hope it's something truly earth shattering, like Knuth getting an e-mail address.

However mundane it might actually end up being, I bet it doesn't trump the "announcement that will redefine how cities are built" turning out to be a goofy little scooter.

He had an email address. He gave it up in the early 90s, when he decided that 15 years of email was enough for any man.

http://www-cs-faculty.stanford.edu/~knuth/email.html

Given the venue, presumably the announcement will be TeX related.

omg what if he came up with a decent syntax for tex? that would be truly earth shattering.

He's an excellent computer scientist but he's never claimed to be a good language designer ;)

LaTeX to be renamed iLaTeX, and Knuth will be creating a group to approve articles written in it, to make sure they don't tarnish its image in any way.

Good joke.

Only--Knuth isn't the author of LaTeX.

OK, so all LaTeX documents will have to be rewritten in pure TeX, because using an extra translation layer produces substandard results.

That's better. (And I'll stop nitpicking.)

And Jobs isn't the inventor of Objective-C.

Nah, you're all wrong. It's actually this: http://www.ibiblio.org/Dave/Dr-Fun/df200002/df20000210.jpg

I'm hoping he's discovered if P=NP.

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.

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.

or perhaps he can break RSA in polynomial time or something like that

Pretty sure that's the same thing as proving P=NP.

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 comment

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.

or maybe he's finished another book!!!! :)

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.

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.

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?

You either had to be very, very delicate or you had to spread the knowledge to too many people before they can react properly.

Someone announcing P=NP in a non-delicate way is part of Charlie Stross's story "Antibodies".

Assuming that it would be a very complex proof, it might take a while for practical applications to be able to catch up.

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?

This reminds me of the buggy-whip analogy. Cryptography vendors will be screwed. Security vendors might have a chance.

That's exactly what I thought the moment I saw this. The other options are a working quantum computer or he's retiring.

I would start thinking badly of him if he referred to his retirement announcement as "earthshaking".

Why not? In addition, he could demostrate that any given NP problem can be solved in O(N^2) time complexity.

Haha, good but http://en.wikipedia.org/wiki/Time_hierarchy_theorem says no.

As if that could stop Knuth...

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.

I guess that'll be impossible.

I doubt he'd wait until the TeX speaking role to announce that.

That is obviously wrong as there's an N in there. CS professors will tell you the same.

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."

Or P=0.

aha

Sarcasm?

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.

Are you trying to make some kind of joke? NP = “nondeterministic polynomial time”, and it is a complexity class of computation problems.

Dammit you beat me to it :-)

Might it be sarcasm/parody? This can be conveyed with unnecessary capital lettering.

Hyperbole, probably.

A magical text with an unbelievable price.

TeX's version number will converge to pi ahead of schedule?

I think announcement the Pi-version number of Tex is the right guess. From the Wikipedia entry ( http://en.wikipedia.org/wiki/TeX ) that is when Tex freezes and no more bug fixes are allowed (every behavior from that point on is a required backwards compatible feature).

Knuth has proven pi is not transcendental and is changing the versioning to use the Prouhet-Thue-Morse constant

More earthshaking: TeX's version number will never converge to pi?

Knuth rewrote himself in MMIX. Fully-documented MMIX.

Maybe he has a designated successor for TAOCP?

I would laugh if it was just something mundane, done in total Andy Kauffman style.

Maybe he is doing a pipe organ concert.

To connect this with the 29 other stories here, Literate Programming is also now no longer permitted on the App Store. Tangle and weave on the Android if you must.

It's a funny comment, but not really true.

The ctangle program would just strip the comments (both C/C++ comments and TeX commentary) out of a .w file and re-arrange the C/C++ code to the order that the compiler would need to see it. While many other tools would leave tell-tale traces of machine-generated code, the C or C++ files generated by ctangle are really indistinguishable from human-written code, because they are the original human-written code. So Apple couldn't tell that you used Literate Programming, nor would it violate the spirit of the rules. Now I wonder how many people use Literate Programming to program for the iPhone. My guess is zero, which is too bad.

It would not violate the spirit but it would violate the letter of the contract. Apple requires that "applications must be originally written in Objective-C, C, C++, or JavaScript" and CWEB is neither. Apple forbids literate programs -- only illiterate programs will be permitted in the App Store.

> the C or C++ files generated by ctangle are really indistinguishable from human-written code

The C or C++ files are typically pretty easy to distinguish from code written by normal human beings (no comments, weird formatting, etc.; more ambiguously, LP tends to produce larger functions/methods because you can break things out as LP sections rather than using the facilities of the underlying language), but there wouldn't be any sign of that in the object code. (Not even the larger functions, necessarily, since the compiler could inline them.)

He's getting a job at Google?

gmail product manager? :)

To announce he will be posing for a new "Programming, you're doing it wrong" poster.

That's John McCarthy, inventor of Lisp.

There's also one with Djikstra. Knuth would make a fitting motive, too. Especially for documentation.

He has solved the halting problem?

He has halted the problem solving?

He's going to write and direct a musical adapted from "The Art Of Computer Programming"

Maybe it was hyperbole on his part?

Quite possible!

It could be LaTeX v3... that's been in progress for so long that any major news would be a shock.

My guess (sure, I'll add to the noise): he's designating successors for the care, feeding, and future development of TeX. He's "retiring" from TeX. Hence the lead in to the panel session that follows.

But that's just a guess.

Maybe he rewrote TAOCP in C?

So it can be read with the iPhone?

He's geting a job at Apple and his books will only be able in the iTeX format ?

Just so Tex and Latex stay the same, I'll be happy :-)

Is he retiring?

This is his retirement. He retired in order to have time to finish the series.

He took emeritus status several years ago.

He's unlikely to stop working on things that interest him.

Earthshaking like the Segway promise?

He's behind all of the earthquakes of late!

Expect the unexpected; He has made a lateral move into an entirely different business: The porn industry. I do not think he can possibly offer more than he already has to CS so he will now focus on contribution that will primarily benefit the degenerates among us. I believe I heard Paul Graham stating that he would do this as well when he was done with YC as after all he is a man of the future. It's all about staying ahead and being flexible about business.

Most unexpected so far!

As Paul Graham said "If you can find a way to turn dicking around into a profitable activity then by all means do it!" on his speech on him entering the porn industry(will add source later)

Jill Knuth is really James Randi.

Has Knuth even looked at TeXmacs yet?

Perhaps he is ignoring it on purpose?

Reply on news.ycombinator.com