Abstract
Existing definitions of the relativizations of NC 1, L and NL do not preserve the inclusions \({{\bf NC}^1 \subseteq {\bf L}, {\bf NL}\subseteq {\bf 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 \({\{{\bf AC}^0 (m), {\bf TC}^0, {\bf NC}^1, {\bf L}, {\bf NL}\}}\) implies the collapse of their relativizations. Next 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. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Klaus Aehlig (2010). Parallel Time and Proof Complexity. Habilitation, Ludwig-Maximilians-University, Munich.
Klaus Aehlig, Stephen Cook & Phuong Nguyen (2007). Relativizing Small Complexity Classes and their Theories. In 16th EACSL Annual Conference on Computer Science and Logic, 374–388. Springer. LNCS 4646.
Mix Barrington David A., Immerman Neil., Straubing Howard (1990) On Uniformity within NC 1. Journal of Computer and System Sciences 41(3): 274–306
Jonathan Buss (1986). Relativized Alternation. In Proceedings Structure in Complexity Theory Conference, 66–76. Springer.
Samuel Buss (1987). The Boolean formula value problem is in Alogtime. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 123–131.
Cook Stephen (1985) A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1–3): 2–22
Stephen Cook & Phuong Nguyen (2010). Logical Foundations of Proof Complexity. ASL Perspectives in Logic Series. Cambridge University Press.
Neil Immerman (1999). Descriptive Complexity. Springer.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Richard Ladner & Nancy Lynch (1976). Relativization of Questions About Log Space Computability. Mathematical Systems Theory 10, 19–32.
Nguyen Phuong, Cook Stephen (2006) Theories for TC 0 and Other Small Complexity Classes. Logical Methods in Computer Science 2(1): 1–40
P. Orponen (1983). General Nonrelativizability Results for Parallel Models of Computation. In Proceedings, Winter School in Theoretical Computer Science 194–205
Walter Ruzzo (1981). On Uniform Circuit Complexity. Journal of Computer and System Sciences 22, 365–383
Ruzzo Walter, Simon Janos, Tompa Martin (1984) Space-Bounded Hierarchies and Probabilistic Computations. Journal of Computer and System Sciences 28(2): 216–230
Istvan Simon (1977). On some subrecursive reducibilities. Ph.D. thesis, Stanford University.
Takeuti Gaisi (1995) Separations of Theories in Weak Bounded Arithmetic. Annals of Pure and Applied Logic 71: 47–67
Christopher Wilson (1987). Relativized NC. Mathematical Systems Theory 20, 13–29
Wilson Christopher (1988) A Measure of Relativized Space Which Is Faithful with Respect to Depth. Journal of Computer and System Sciences 36: 303–312
Zambella Domenico (1996) Notes on Polynomially Bounded Arithmetic. Journal of Symbolic Logic 61(3): 942–966
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aehlig, K., Cook, S. & Nguyen, P. Relativizing small complexity classes and their theories. comput. complex. 25, 177–215 (2016). https://doi.org/10.1007/s00037-015-0113-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-015-0113-8