Publication:260396

DOI10.1007/978-3-540-74915-8_29zbMath1336.68084arXiv1204.5508OpenAlexW2276406710MaRDI QIDQ260396

F. Blanchet-Sadri, M. Dambrine

Publication date: 21 March 2016

Published in: Computational Complexity, Computer Science Logic (Search for Journal in Brave)

Abstract: Existing definitions of the relativizations of NCOne, L and NL do not preserve the inclusions $NCOne subseteq L$, $NLsubseteq ACOne$. 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 ${ACZm, TCZ, NCOne, L, NL}$ implies the collapse of their relativizations. Next we exhibit an oracle $alpha$ that makes $ACk(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 Ptime 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.

Full work available at URL: https://arxiv.org/abs/1204.5508

zbMATH Keywords

proof complexitycomplexity classeslogical theoriesrelativized classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativizing small complexity classes and their theories
• Space-bounded hierarchies and probabilistic computations
• A measure of relativized space which is faithful with respect to depth
• On uniform circuit complexity
• Separations of theories in weak bounded arithmetic
• On uniformity within \(NC^ 1\)
• A taxonomy of problems with fast parallel algorithms
• RelativizedNC
• Relativization of questions about log space computability
• Theories for TC0 and Other Small Complexity Classes
• Notes on polynomially bounded arithmetic

Related Items (4)

Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ Induction rules in bounded arithmetic ⋮ The complexity of the comparator circuit value problem ⋮ Relativizing small complexity classes and their theories

This page was built for publication: Relativizing small complexity classes and their theories