Relativizing Small Complexity Classes and Their Theories

Abstract Existing definitions of the relativizations of NC 1, L and NL do not preserve the inclusions NC 1 ⊆ L, NL ⊆ AC 1. We start by giving the first definitions that preserve them. Here for L 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 { AC 0 ( m ), TC 0, NC 1, L, NL } implies the collapse of their relativizations. Next we develop theories that characterize the relativizations of subclasses of P 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. Finally we exhibit an oracle α that makes AC k ( α ) 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.

Authors

• Klaus Aehlig
• Stephen A. Cook
• Phuong Nguyen 0001

Keywords

No keywords are indexed for this paper.