Logo Logo
Switch Language to German

Aehlig, Klaus; Cook, Stephen and 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'.


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.

Actions (login required)

View Item View Item