2012/04/24 by Klaus Aehlig, Aehlig, Klaus, Stephen Cook +3
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1204.5508
28 pages
arxiv created 2012/04/24 · openalex publication_date 2012/04/24 · arxiv updated 2012/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Existing definitions of the relativizations of \NCOne, Ł and \NL do not preserve the inclusions \NCOne ⊆ Ł, \NL⊆ \ACOne. We start by giving the first definitions that preserve them. Here for Ł 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, Ł, \NL\ implies the collapse of their relativizations. Next we exhibit an oracle α that makes \ACk(α) 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.