5 ms·
I'm hoping he's discovered if P=NP.
by baddox 17y ago
I'm hoping he's discovered if P=NP.
- kloncks 17y agoThat 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.
- sswam 17y agoor perhaps he can break RSA in polynomial time or something like that
- deleted 17y ago[deleted]
- noamsml 17y agoPretty sure that's the same thing as proving P=NP.
- meami 17y agoHMAC/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"
- Locke1689 17y agoNo 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 17y ago[deleted]
- PG-13 17y agoYeah.... 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.
- sswam 17y agoor maybe he's finished another book!!!! :)
- baddox 17y agoFrom 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.
- faragon 17y agoWhy not? In addition, he could demostrate that any given NP problem can be solved in O(N^2) time complexity.
- eru 17y agoI guess that'll be impossible.
- jrp 17y agoHaha, good but http://en.wikipedia.org/wiki/Time_hierarchy_theorem http://en.wikipedia.org/wiki/Time_hierarchy_theorem says no.
- tjr 17y agoAs if that could stop Knuth...
- faragon 17y agoBut 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.
- Dellort 17y agoThat is obviously wrong as there's an N in there. CS professors will tell you the same.
- orp 17y agoSarcasm?
- Dellort 17y agoUse 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.
- jacobolus 17y agoAre you trying to make some kind of joke? NP = “nondeterministic polynomial time”, and it is a complexity class of computation problems.
- TimothyFitz 17y agoThe way my prof told it: "I'm really not sure why people keep asking if P=NP. Of course it does, when N=1."
- richcollins 17y agoDammit you beat me to it :-)
- elblanco 17y agoThat's exactly what I thought the moment I saw this. The other options are a working quantum computer or he's retiring.
- BoppreH 17y agoI would start thinking badly of him if he referred to his retirement announcement as "earthshaking".
- philwelch 17y agoSomething 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.
- tetha 17y agoYou either had to be very, very delicate or you had to spread the knowledge to too many people before they can react properly.
- arethuza 17y agoSomeone announcing P=NP in a non-delicate way is part of Charlie Stross's story "Antibodies".
- rlpb 17y agoAssuming that it would be a very complex proof, it might take a while for practical applications to be able to catch up.
- dmoney 17y agoHow 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?
- rlpb 17y agoThis reminds me of the buggy-whip analogy. Cryptography vendors will be screwed. Security vendors might have a chance.
- ramchip 17y agoI 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.
- nopassrecover 17y agoI doubt he'd wait until the TeX speaking role to announce that.