31–40 of 116 posts
There's some speculation about where the next breakthroughs will come from at the end of the chapter; it will be interesting to look back in 10-20 years and see if Knuth was correct.
A surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.
There's some speculation about where the next breakthroughs will come from at the end of the chapter; it will be interesting to look back in 10-20 years and see if Knuth was correct.
A surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.
“At the present time very few people believe that P=NP. In other words, almost everybody who has studied the subject thinks that satisfiability cannot be decided in polynomial time. The author of this book, however, suspects that N^O(1)-step algorithms do exist, yet that they’re unknowable. Almost all polynomial time algorithms are so complicated that they lie beyond human comprehension, and could never be programmed for an actual computer in the real world. Existence is different from embodiment.”
But would the existence of such "step algorithms" be fully equivalent to P=NP or a limited case applicable to only a subset of NP problems (i.e. one's thought previously to be NP)?
I don't know the answer and am genuinely curious.
Earlier quoted context omitted.
I am not sure how it is related to 2015. I actually prefer a ps file that I can render to a PDF easily instead a Javascript heavy messy website where everything is distracting you from the content. On the top of that Knuth invented Tex to be able to write scientific documentations with ease[1]. 1. https://en.wikipedia.org/wiki/TeX
I vastly prefer HTML with searchable text, easy copy-pasting capability, easy indexability, etc. to PDF with its outdated printed-page metaphor. On the other hand, it's Knuth and TAOCP, so I can't really complain much.
Does Knuth have a protege, helping him today, and to carry on the task should it take decades still? Also, is there a condensed version of his work that preserves the spirit and rigor?
> Also, is there a condensed version of his work
> that preserves the spirit and rigor ?
Chapter 7 will eventually fill at least four volumes . . . assuming that I'm able to remain healthy. Apparently TAOCP has a lot in common with the Wheel of Time. I have a ton of respect for these huge, decades-long, life-defining projects and the people who undertake them (Robert Caro's LBJ biography is another example.) So the end of this project always receding further into the distance makes me wistful, even if th…
"You can have a sneak preview... As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions." If you want to frame one of those cheques, get in fast.
Is it reasonable to study the second edition, or should I buy a copy of the third edition? I've been a hobbyist programmer for 20+ years, and I'd like to strengthen my understanding of basic data structures.
Earlier quoted context omitted.
A surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.
I too saw this footnote near the beginning (page 9): “At the present time very few people believe that P=NP. In other words, almost everybody who has studied the subject thinks that satisfiability cannot be decided in polynomial time. The author of this book, however, suspects that N^O(1)-step algorithms do exist, yet that they’re unknowable. Almost all polynomial time algorithms are so complicated that they lie beyo…
One way to think of this is in terms of galactic algorithms, which are algorithms that incrementally improve the exponent in a polynomial time algorithm, but have constant terms so huge that they're effectively useless, practically. He's suggesting that there could exist a polynomial time algorithm for an NP problem which is similarly useless - but with the additional caveat that we won't even be able to prove theorems about it!
Earlier quoted context omitted.
A surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.
I too saw this footnote near the beginning (page 9): “At the present time very few people believe that P=NP. In other words, almost everybody who has studied the subject thinks that satisfiability cannot be decided in polynomial time. The author of this book, however, suspects that N^O(1)-step algorithms do exist, yet that they’re unknowable. Almost all polynomial time algorithms are so complicated that they lie beyo…
I just picked up my father's old copy of vol. 1, Fundamental Algorithms . It's amazing that a book published in 1973 (second edition) can still be worth studying. I'd like to work from the copy I have, largely for sentimental reasons. My father passed away a few years ago, and it feels really good to work from the same book he studied decades ago. Is it reasonable to study the second edition, or should I buy a copy o…
For anyone curious, this section is on SAT solving. It's section 7.2.2.2 of TAOCP, and is over 300 pages long. Pretty thorough for a section of backtrack, within a section on generating all possibilities, within a full chapter on combinatorial searching.
What I'm saying is that there's plenty of literature on SAT Solving already, and some of it is probably better.
