GHZ wrote:But, the whole middle 2/3s of Anathem, especially the random philosophy is just bad. It just doesn't make sense mostly. I'm kind of shocked. I'm a professional physicist, working in the area of quantum computing, and I found the discussions of computers, technology, etc... in Cryptonomicon and Baroque Cycle to be excellent, in fact those books taught me some new stuff about topics I thought I knew. But, the physics-inspired philosophy of Anathem is just wrong. To take an example, there is the comment about using quantum computers to solve travelling salesman. In fact, there's no reason to believe that they can do this in polynomial time. Certainly no one can prove they can't, because no one can even prove that classical computers can't, but we at least know that you can't just create a superposition of solutions and pick the one which works, which is what is claimed to happen in the book. This is just one example, it's really all pretty off, and I don't know what happened in this book compared to all his previous ones. Btw, I did like the philosophical discussions in Baroque Cycle, so it's not that I don't like philosophy..
Well, Stephenson's hardly the first one to suggest a Nondeterministic Turing Machine via quantum computing. And there is reason to suppose that given an NTM like you just described, you can do it in polynomial time. It's NP-Hard=Non-Polynomial Hard. Meaning that you can do it in polynomial time with an NTM. Of course, I'm sure the proof is something I wouldn't understand.
PS I haven't actually read Anathem, but I'd like to. I really liked the Waterhouse/Shaftoe parts of Cryptonomicon/Baroque Cycle, but hated Eliza.