From: Barak Pearlmutter (bap@cs.unm.edu) Subject: Re: Fire on the Deep, zones? Newsgroups: rec.arts.sf.written Date: 1997/02/25 All your speculations here are quite incorrect. They would all lead to only a constant factor speedup between the zones, which would be unable to give rise to the effects described in the novel. The difference between the zones is strongly hinted at a couple times. (And keep in mind that Vinge is a professor of Comp Sci.) - The ship's cargo includes a one-time pad. Why not use strong encryption, like RSA? Note that strong encryption of that sort becomes *more* feasible rather than less feasible as computers become faster, because the gap between the encoder and the cryptanalyst *grows*! (Assuming current models of computation.) - Pham questions this, and says they should use public-key cryptography instead. He is laughed at, and it is explained to him that public-key cryptography is not secure in the beyond. Why? - Some mysterious *calculation* is needed to make a "jump", and if you can't make it fast enough (presumably before something has changed out from under you) you can't jump at all. There can be only one explanation: our models of computation break down. The complexity class that can be realized by physical computers is *different* in the beyond than in the slow zone. Eg, NP-hard problems take only polynomial time to solve, so the code-breakers gain the advantage over the code-makers. The zones correspond to different complexity classes. In the depths, the complexity class P is not physically realizable. Instead something like Poly-Log is all that can be calculated in polynomial *physical* time. In the slow zone, the complexity class we call P can be calculated by an actual computer in polynomial time. In the beyond, even more can be done. There are levels of the beyond, corresponding to more difficult gradations of NP-hard problems becoming accessible. And in the transcend, even undecidable problems become soluble. There are also some strong hints that the zones are set up via particles of some sort, under some kind of mutual long-range attraction. In the unthinking depths, these particles form a solid. That's why the transition between the slow zone and the unthinking depths is so abrupt and stable. In the slow zone the particles form a liquid, allowing more computational mobility. That's why there are no gradations within the slow zone, and why the transition between the slow zone and the beyond has waves at various scales, foam-like regions, etc. In the beyond, the particles are a gas. The pressure is high in the low beyond, so their density is high. Towards the high beyond, the pressure is getting lower, and so computation gets even faster. In the transcend, these particles are no longer present, ie there is a vacuum of these computation-inhibiting particles. That's why the boudary between the beyond and the transcend is so gradual, with no abrupt transition whatsoever. Vinge was basically making a joke: he was building a cosmology on the principles of theoretical computer science, rather than on the more usual principles of physics. As a postscript, I should note that if we can actually build quantum computers, we may not actually reside in the slow zone, by these definitions. Ie it may be physically possible to solve problems in QP (quantum polynomial) in polynomial physical time, and there exist problems known to be in QP which are believed to not be in P. It is even possible that QP = NP, we don't know yet. Vinge knew this when he wrote the book. -- Barak Pearlmutter <bap@cs.unm.edu>, http://www.cs.unm.edu/~bap/