Relativizing small complexity classes and their theories

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

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.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1016-3328
• Language: English