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.
I also liked the Fermatesque "exercise 223 is also currently unsolved, although I've rated it only '40' because I once thought of an answer (which I have since forgotten!)".
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 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)?
taosat|10 years ago
Proponents of RSA, DHE crypto - take note.
schoen|10 years ago
michaelsbradley|10 years ago
“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.
rasz_pl|10 years ago
unknown|10 years ago
[deleted]