Michele Reilly

This begins a series of questions that I examine regarding the relationship between time and space.

I refer to what I consider physically realizable complexity classes which I believe would be useful to consider for some of our most foundational computational questions in science today. Contemporary computer scientists refer to so-called complexity class hierarchies, without regard for adjustments to these classes for instance with respect to heat and their implementation in a real physical universe with finite resources.

The argument about physical computational complexity is pretty straightforward, and rises from the physics of reversible and quantum computation. Memory space is identified with negentropy: S_max – S = how far we are from maximum entropy.   In a quantum computer in a pure state, S=0, and memory space is just the number of qubits in the computer. If performing a logic operation generates any entropy at all, which is the case, for example, in which there is some probability of making an error, then performing a logic operation must also use up some memory space, even if it is only a small amount per operation (fraction of a bit).

Consequently, the physical memory space taken up by a computation is proportional to the number of operations performed during the computation.    It is not possible to use only polynomial physical memory space for a computation that takes exponential time.    Hence PhyP =PhyPSPACE.

Further studies I am interested in here remove the scientific matter and energy paradigm, and are about whether our best cosmological theories can be recast in a purely quantum and classical computational manner. I believe this delineation could conceivably provide implications for our best scientific theories, and inform, or even rule out existing matter/energy models, if both known and new complexity classes (based on the character of physical law, ie adjustments for entropy dissipation, including with quantum logic gates) displayed certain equivalences.

For instance, the notion of a risk in a game might be evaluated using frequencies or Bayes’s rule. But there are games with unknown underlying distributions and these might more effectively be considered not to be paradoxes, when understood computationally. Take as an example the Ellsberg paradox, one might simply say due to the halting problem that is it not irrational to refuse to play a game with unknown parameters i.e. a Turing machine or distribution of unknown Turing machines, since the urn itself represents an unknown Turing machine. That is an example of a spatially finite game. Scientific models can contain within them the same sort of so-called paradoxes, when not properly ontologized. We ask whether the theory of computation, when applied to betting containers, either infinite (cosmological theories) versus finite ones, “urns” within space (versus time) can help rule out or shed light on irregularities previously thought to be paradoxes. 

1-2 below can be thought of as different computational claims requiring more explanation than what I provide here.

A language L is in BQP if and only if there exists a polynomial time quantum Turing machine (or family of quantum circuits) that accepts L with a certain error probability: Quantum algorithms accepting decision problems in reasonable amounts of time. This is to say nothing of spacial constraints for the moment.

Everything in PSPACE is interconnected: A pre-established harmony, if you will, or the best of all possible worlds in Leibnitz’s sense of things. It is a form of being, but not in-time: Every bit’s configuration can be selected in a manner which takes into account every other bit.  PSPACE implies bits can be “fully optimized” in some manner. PSPACE means we have classical bits being laid down, as the output of some exhaustive, and possibly even quantum search, when you take as a starting point our universe to be a quantum multiverse.

Morally speaking here, rather than: “What can be figured out is a matter of how much time you have.” It is instead: “What we can figure out, is actually a matter of how much memory (or perhaps more realistically, free energy) that we have.”  The content of memory is whatever is optimal for some agent’s criterion.  PSPACE is like a Parmenidian block universe. In such a world, “the past” doesn’t ultimately leave a record. 

For this argument, please refer to an overview here.

More physical complexity class relationships will be considered in future letters.