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.
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.
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.
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.
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.
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.
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?
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 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).
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.
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.)
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.
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.
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)
But that's no fun, so I hope it's something truly earth shattering, like Knuth getting an e-mail address.