<p>In this paper <a href="https://people.cs.rutgers.edu/%7Eallender/papers/pl3.pdf" rel="nofollow noreferrer">https://people.cs.rutgers.edu/~allender/papers/pl3.pdf</a> Mitsu Ogihara and I show that the &quot;oracle&quot; #L hierarchy (and related classes) with the Ruzzo-Simon-Tompa access mechanism corresponds exactly to the AC^0 hierarchy over #L.  Thus, in at least this instance, the RST access mechanism corresponds nicely to the natural &quot;circuits-with-oracle-gates&quot; formalism.</p>

CC BY-SA 4.0
2023-10-01T00:58:46.153Z
2023-10-01T00:58:46.153Z
Eric Allender
<p>A definition of oracle access that works for small circuit complexity classes (the $AC^k$ and $NC^k$ hierarchies) as well as for logarithmic space classes, with the property that all known inclusions relativize, can be found in this paper: </p>

<p><a href="http://www.springerlink.com/content/6646254324g645p7/">Klaus Aehlig, Stephen Cook and Phuong Nguyen: Relativizing Small Complexity Classes and their Theories, CSL 2007, Springer LNCS 4646</a> </p>

CC BY-SA 3.0
2012-06-14T04:51:26.577Z
Thanks for the pointer. But I still don't have a clear idea as to how RST applies to circuits with oracle gates. I hope you don't mind if I wait for a while to see if there are any other interesting takes on this issue, before accepting your answer.
Nikhil
CC BY-SA 3.0
2012-06-13T15:00:26.963Z
2012-06-13T15:00:26.963Z
Jan Johannsen
<p>In a <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/LLspace.pdf">paper</a> on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some
more pathological examples in this vein in the literature. I have been reading some papers on relativized small space classes, and one of the primary tools in this area is the <a href="http://www.sciencedirect.com/science/article/pii/0022000084900667">Ruzzo-Simon-Tompa</a>(RST) oracle access mechanism which demands that a non-deterministic space-bounded turing machine act deterministically while making queries to the oracle. </p>

<p>Now consider circuit families with oracle gates - say, $A^B$, where $A$ is a circuit complexity class containing logspace with oracle access to another class $B$, via oracle gates appended to the basis of $A$. Are there any pathological examples similar in spirit to the Ladner-Lynch paper, known for such classes? What would be a RST-like restriction necessary for such classes?
In case there are indeed such examples, am I right in guessing that a RST analogue would be to insist that $A$ be a logspace-uniform circuit family?</p>

<cc.complexity-theory><complexity-classes><circuit-complexity><oracles><relativization>
Ruzzo-Simon-Tompa oracle access mechanism
Nikhil
# Ruzzo-Simon-Tompa oracle access mechanism

(Asked by: username_0 on 2012-06-13)

In a [paper](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/LLspace.pdf) on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some
more pathological examples in this vein in the literature. I have been reading some papers on relativized small space classes, and one of the primary tools in this area is the [Ruzzo-Simon-Tompa](http://www.sciencedirect.com/science/article/pii/0022000084900667)(RST) oracle access mechanism which demands that a non-deterministic space-bounded turing machine act deterministically while making queries to the oracle.

Now consider circuit families with oracle gates - say, $A^B$, where $A$ is a circuit complexity class containing logspace with oracle access to another class $B$, via oracle gates appended to the basis of $A$. Are there any pathological examples similar in spirit to the Ladner-Lynch paper, known for such classes? What would be a RST-like restriction necessary for such classes?
In case there are indeed such examples, am I right in guessing that a RST analogue would be to insist that $A$ be a logspace-uniform circuit family?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, oracles, relativization

---

## 2 answers

### Answer by username_2 on 2012-06-13. Score: 9 | Accepted answer

A definition of oracle access that works for small circuit complexity classes (the $AC^k$ and $NC^k$ hierarchies) as well as for logarithmic space classes, with the property that all known inclusions relativize, can be found in this paper:

[Klaus Aehlig, Stephen Cook and Phuong Nguyen: Relativizing Small Complexity Classes and their Theories, CSL 2007, Springer LNCS 4646](http://www.springerlink.com/content/6646254324g645p7/)

> **Comments:**
> **username_0**: Thanks for the pointer. But I still don't have a clear idea as to how RST applies to circuits with oracle gates. I hope you don't mind if I wait for a while to see if there are any other interesting takes on this issue, before accepting your answer.  

---

### Answer by username_1 on 2023-10-01. Score: 3

In this paper [https://people.cs.rutgers.edu/~allender/papers/pl3.pdf](https://people.cs.rutgers.edu/%7Eallender/papers/pl3.pdf) Mitsu Ogihara and I show that the "oracle" #L hierarchy (and related classes) with the Ruzzo-Simon-Tompa access mechanism corresponds exactly to the AC^0 hierarchy over #L. Thus, in at least this instance, the RST access mechanism corresponds nicely to the natural "circuits-with-oracle-gates" formalism.


---

