Relativizing Small Complexity Classes and their Theories

Details Relativizing Small Complexity Classes and their Theories Relativizing Small Complexity Classes and their Theories

2012-04-24

arxiv.org/abs/1204.5508v1

Computer Science

Computational Complexity

28 pages

Scientific paper

Existing definitions of the relativizations of \NCOne, \L\ and \NL\ do not preserve the inclusions $\NCOne \subseteq \L$, $\NL\subseteq \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.

Affiliated with

Also associated with

No associations

Rating

Relativizing Small Complexity Classes and their Theories does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relativizing Small Complexity Classes and their Theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relativizing Small Complexity Classes and their Theories will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137052