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.
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).
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.
HMAC/SHA-512 Tests
HMAC/SHA-512 Short ASCII Text:
HMAC/SHA-512 Short Hex Key:value="0123456789:;<=>?@ABC0123456789:;<=>?@ABC"
HMAC/SHA-512 Short Hex Result:
value="74ed1131b8e37c0e18829b7ae7d99925664cfe055c2d01fa00d0f152ac321a50f3ef1ee91a36fd6248de60ede4196a4f9e5acca4981a09a91a0745d674ca11d3"
HMAC/SHA-512 Med ASCII Text:
HMAC/SHA-512 Med Hex Key: value="000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f"
HMAC/SHA-512 Med Hex Result:
HMAC/SHA-512 Med Correct:value="e3c46b747b407ae103d75d94cc2247d6fef607a019e9dca6a1183966a163eb19317e7642da27b6e6ed22fea8224c493d5f20a458f83a555b94264253ddceb242"
HMAC/SHA-512 Large Hex Text:
value="53616D706C65202333"
HMAC/SHA-512 Large Hex Key:value="505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3"
HMAC/SHA-512 Large Hex Result:
HMAC/SHA-512 Large Correct: value="a2a8627f166e8c52d95fbf5c55271d466d43b73696e94977d08262f021d9a916f9d10f09f40db64e038c2ed3b16fbb9e61082c9173acfa86445612ccd4d8836c"
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.
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.
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?
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.
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.
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)
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.)
93 comments
[ 4.4 ms ] story [ 119 ms ] threadHe's unlikely to stop working on things that interest him.
Only--Knuth isn't the author of LaTeX.
I think it might be one of the few, if not the only thing, that would live up to that.
HMAC/SHA-512 Short Hex Result: value="74ed1131b8e37c0e18829b7ae7d99925664cfe055c2d01fa00d0f152ac321a50f3ef1ee91a36fd6248de60ede4196a4f9e5acca4981a09a91a0745d674ca11d3"
HMAC/SHA-512 Med ASCII Text:
HMAC/SHA-512 Med Hex Key: value="000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f"
HMAC/SHA-512 Med Hex Result:
HMAC/SHA-512 Med Correct:value="e3c46b747b407ae103d75d94cc2247d6fef607a019e9dca6a1183966a163eb19317e7642da27b6e6ed22fea8224c493d5f20a458f83a555b94264253ddceb242"
HMAC/SHA-512 Large Hex Text: value="53616D706C65202333"
HMAC/SHA-512 Large Hex Key:value="505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3"
HMAC/SHA-512 Large Hex Result: HMAC/SHA-512 Large Correct: value="a2a8627f166e8c52d95fbf5c55271d466d43b73696e94977d08262f021d9a916f9d10f09f40db64e038c2ed3b16fbb9e61082c9173acfa86445612ccd4d8836c"
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.
My favorite conspiracy theory is that P = NP and the NSA is covering it up.
The problem is: will humanity find a feasible algorithm?
But that's no fun, so I hope it's something truly earth shattering, like Knuth getting an e-mail address.
http://www-cs-faculty.stanford.edu/~knuth/email.html
Perhaps he is ignoring it on purpose?
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.
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.)