6 ms·
Twenty Questions for Donald Knuth (2014)
- _asummers 9y agoI am certainly never one to question Donald Knuth on things in computer science, but I've always thought his opinion of P vs. NP an odd one, though he is certainly not the only person with that opinion.
- napsterbr 9y agoYou'll definitely enjoy this: https://www.cs.umd.edu/~gasarch/papers/poll.pdf https://www.cs.umd.edu/~gasarch/papers/poll.pdf Edit: sorry, misread your comment, thought you were wondering what was Knuth's opinion. Still, I'll leave the link here, since it's a great read nonetheless
- albertzeyer 9y agoFor the lazy people, from that document: > Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P=NP because there are only finitely many obstructions to the opposite hypothesis”; hence there will exists a polynomial time solution to SAT but we will never know its complexity!
- thomasahle 9y agoI think he just got tired of being asked the question and decided to start messing around.
- bitexploder 9y agoHis reasoning felt solid to me. Even if it turns out to be true it is unlikely to be useful, which is borne out by the lack of algorithms and research that have come close to cracking it, despite the effort of many.
- dx034 9y agoAnyone here who can honestly say that they worked through all volumes (obviously not answering everything)? I often hear people talk about it but never met anyone in real life who actually did this.
- wiz21c 9y agoI read the pseudo random number generation very carefully and skimmed around the rest. But reading everything...
- SuperGent 9y agoI'm sure Donald Knuth has! Seriously, this is a life goal for me to read and understand these works, especially after I read that Bill Gates said he would hire anyone that had done.[0] Not sure that its going to happen though, as the maths is slowing me down! [0]http://www.independent.co.uk/news/business/bill-gates-once-said-definitely-send-me-a-r-sum-if-you-finish-this-fiendishly-difficult-book-a7020701.html http://www.independent.co.uk/news/business/bill-gates-once-s...
- jackfoxy 9y agoI read all 3 volumes of the 2nd edition in the 90s. A couple of the long difficult proofs I glossed over. IIRC I read all the problems, but can't say I worked through very many. Vol 4a is on the coffee table in my office and I occasionally read some random passage.
- hackermailman 9y agoWorking through the volumes is possible: http://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art055 http://commandlinefanatic.com/cgi-bin/showarticle.cgi?articl... I read the volumes roughly 30mins a day, and try most of the exercises. Like the above linked blog post I at least attempt to just understand the question on the M[40]+ exercises which still can teach you something by merely understanding why it's a difficult problem.
- mhh__ 9y agoI'm sure someone has. If I was interested enough I supposed I could over a sufficiently long length of time? I do love reading Knuth, but I struggle with sticking with single books/topics for long lengths of time so I doubt I could keep it up for all the volumes.
- deleted 9y ago[deleted]
- DataWorker 9y agoInteresting demarcation he makes between geeks and mathematicians and scientific thinkers more generally. Would be curious what the identifying traits of geeks are in his mind, though one can make some guesses given the examples he cites.
- Zarathust 9y agoI was kind of expecting 12 more
- smitherfield 9y agoOr C more. :)
- flavio81 9y ago1100 more!
- debacle 9y agoIt's interesting how this article made it to HN - From the post about the potential proof surrounding P != NP yesterday, there was a great comment thread on a bit of the history of proofs, where this link was shared.