<p>The best reference for relativized circuits is Chris Wilson's paper &quot;Relativized NC&quot;  <a href="https://doi.org/10.1007/BF01692056" rel="nofollow noreferrer">Link</a></p>
<p>The second condition you have (downward closure of O_n) is not needed to get the equivalence say between P^O and uniform poly-size circuits with oracle O. Also your third condition should be thrown away, the size of the circuit will prevent access to O_m for m larger than the circuit size.</p>

CC BY-SA 2.5
2010-08-25T16:36:02.737Z
There's no explicit commentary in Wilson's paper on the oracle gates themselves; but in retrospect if you take the oracle seriously as representing membership in a set of boolean strings as with TMs, then my second condition is merely a non-issue (i.e. it goes without saying). By your observation of the superfluousness of my third condition, it then suffices to have an infinite family of gates which decide membership in A for any particular finite string size. That works for me; I wish I had thought of it earler.
Niel de Beaudrap
CC BY-SA 2.5
2010-08-25T16:45:12.953Z
Remarks for the benefit of casual spectators --- Wilson's article defines the depth contribution of an oracle gate on k bits to be ceil(log k), in apparent analogy to prior work by Cook ("A taxonomy of problems with fast parallel algorithms", Inform. and Control, 64). There is a technical issue of whether to allow oracle queries in the process of building the circuits themselves (each of which may also use oracles): he comments that it doesn't seem to matter. In the end, though, he is dissatisfied by existence of A for which NC_1^A is not contained in NSPACE^A(O(n^k)), for any k constant.
Niel de Beaudrap
CC BY-SA 4.0
2010-08-25T15:30:49.907Z
2022-10-09T15:02:30.043Z
2022-10-09T15:02:30.043Z
Lance Fortnow
<p>Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for a given oracle Turing machine?</p>

<p>This may be an elementary question, but it is not obvious where to look, and I'm the sort of person who likes to make sure that my foundations are using good-quality mortar. If there is a standard reference, please point me to it. (Papadimitriou's book, for instance, does not seem to describe circuits with oracles at all.)</p>

<p>My working hypothesis is this: a uniform circuit family with access to an oracle (e.g. for solving an NP-complete problem) is defined as follows:</p>

<ul>
<li><p>One defines an infinite family of "oracle gates" O<sub>n</sub>&nbsp;, one for each circuit size n, each of which compute a function f<sub>n</sub>&nbsp;:&nbsp;{0,1}<sup>cn</sup>&nbsp;&rarr;&nbsp;{0,1} for some constant c.</p></li>
<li><p>The functions f<sub>n</sub> computed by the oracle gates O<sub>n</sub> should be  "uniform" in the following sense: for any n&nbsp;&lt;&nbsp;N and <strong>x</strong>&nbsp;&isin;&nbsp;{0,1}<sup>n</sup>, we require f<sub>n</sub>(<strong>x</strong>)&nbsp;=&nbsp;f<sub>N</sub>(&nbsp;0<sup>c(N&minus;n)</sup>&nbsp;<strong>x</strong>&nbsp;) --- that is, the oracle gates must use a consistent and extensbile "encoding" of their inputs.</p></li>
<li><p>One then defines a uniform circuit family, where the oracle gates are among the allowed operations to the circuit, restricting the circuit for input size n to use the gate O<sub>n</sub>.</p></li>
</ul>

<p>I imagine that some of the choices above may be arbitrarily fixed without losing any generality. What I am interested in is a reference for the correspondence, or at least  a description of how to modify the description above to obtain the standard one.</p>

CC BY-SA 2.5
2010-08-25T16:26:29.897Z
Since I know you work in quantum information, I would recommend John Watrous' survey on Quantum computational complexity, where he also talks about oracles in quantum circuits and querying the oracle in superposition.
Robin Kothari
CC BY-SA 2.5
2010-08-26T00:03:34.440Z
Watrous' article is also a good reference. But what it turned out I needed in this case was to be somehow disabused of the idea that anyone would want to define a relativized circuit family in a way that didn't correspond to just testing the same predicate for different finite string lengths, by being reminded that the semantics of an oracle classically is to indicate membership in some set. As it turned out, drawings of circuit gates with the symbols "∈A?" on them was all I needed.
Niel de Beaudrap
<cc.complexity-theory><turing-machines><oracles><circuit-families>
Circuits with oracles vs. Turing Machines with oracles
Niel de Beaudrap
# Circuits with oracles vs. Turing Machines with oracles

(Asked by: username_0 on 2010-08-25)

Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for a given oracle Turing machine?

This may be an elementary question, but it is not obvious where to look, and I'm the sort of person who likes to make sure that my foundations are using good-quality mortar. If there is a standard reference, please point me to it. (Papadimitriou's book, for instance, does not seem to describe circuits with oracles at all.)

My working hypothesis is this: a uniform circuit family with access to an oracle (e.g. for solving an NP-complete problem) is defined as follows:

* One defines an infinite family of "oracle gates" On , one for each circuit size n, each of which compute a function fn : {0,1}cn → {0,1} for some constant c.
* The functions fn computed by the oracle gates On should be "uniform" in the following sense: for any n < N and **x** ∈ {0,1}n, we require fn(**x**) = fN( 0c(N−n) **x** ) --- that is, the oracle gates must use a consistent and extensbile "encoding" of their inputs.
* One then defines a uniform circuit family, where the oracle gates are among the allowed operations to the circuit, restricting the circuit for input size n to use the gate On.

I imagine that some of the choices above may be arbitrarily fixed without losing any generality. What I am interested in is a reference for the correspondence, or at least a description of how to modify the description above to obtain the standard one.

**Tags:** cc.complexity-theory, turing-machines, oracles, circuit-families
> **Comments:**
> **username_1**: Since I know you work in quantum information, I would recommend John Watrous' survey on Quantum computational complexity, where he also talks about oracles in quantum circuits and querying the oracle in superposition.  
> **username_0**: Watrous' article is also a good reference. But what it turned out I needed in this case was to be somehow disabused of the idea that anyone would want to define a relativized circuit family in a way that didn't correspond to just testing the same predicate for different finite string lengths, by being reminded that the semantics of an oracle classically is to indicate membership in some set. As it turned out, drawings of circuit gates with the symbols "∈A?" on them was all I needed.  

---

## 1 answers

### Answer by username_2 on 2010-08-25. Score: 20 | Accepted answer

The best reference for relativized circuits is Chris Wilson's paper "Relativized NC" [Link](https://doi.org/10.1007/BF01692056)

The second condition you have (downward closure of O\_n) is not needed to get the equivalence say between P^O and uniform poly-size circuits with oracle O. Also your third condition should be thrown away, the size of the circuit will prevent access to O\_m for m larger than the circuit size.

> **Comments:**
> **username_0**: There's no explicit commentary in Wilson's paper on the oracle gates themselves; but in retrospect if you take the oracle seriously as representing membership in a set of boolean strings as with TMs, then my second condition is merely a non-issue (i.e. it goes without saying). By your observation of the superfluousness of my third condition, it then suffices to have an infinite family of gates which decide membership in A for any particular finite string size. That works for me; I wish I had thought of it earler.  
> **username_0**: Remarks for the benefit of casual spectators --- Wilson's article defines the depth contribution of an oracle gate on k bits to be ceil(log k), in apparent analogy to prior work by Cook ("A taxonomy of problems with fast parallel algorithms", Inform. and Control, 64). There is a technical issue of whether to allow oracle queries in the process of building the circuits themselves (each of which may also use oracles): he comments that it doesn't seem to matter. In the end, though, he is dissatisfied by existence of A for which NC_1^A is not contained in NSPACE^A(O(n^k)), for any k constant.  

---

