Paper detail

Relativizing Small Complexity Classes and their Theories

Existing definitions of the relativizations of \NCOne, Ł and \NL\ do not preserve the inclusions $\NCOne \subseteq Ł$, $\NL\subseteq \ACOne$. We start by giving the first definitions that preserve them. Here for Ł and \NL\ we define their relativizations using Wilson's stack oracle model, but limit the height of the stack to a constant (instead of $\log(n)$). We show that the collapse of any two classes in $\{\ACZm, \TCZ, \NCOne, Ł, \NL\}$ implies the collapse of their relativizations. Next we exhibit an oracle $α$ that makes $\ACk(α)$ a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in [Takeuti, 1995]. The idea is that a circuit whose nested depth of oracle gates is bounded by $k$ cannot compute correctly the $(k+1)$ compositions of every oracle function. Finally we develop theories that characterize the relativizations of subclasses of \Ptime\ by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence the oracle separations imply separations for the relativized theories.