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/