Logo Logo
Help
Contact
Switch Language to German
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong (2016): Relativizing small complexity classes and their theories. In: Computational Complexity, Vol. 25, No. 1: pp. 177-215
Full text not available from 'Open Access LMU'.

Abstract

Existing definitions of the relativizations of NC (1), L and NL do not preserve the inclusions . 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 implies the collapse of their relativizations. Next we exhibit an oracle alpha that makes AC (k) (alpha) 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 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, and hence, the oracle separations imply separations for the relativized theories.