13
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Aug 25, 2010 at 16:26
  • $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Aug 26, 2010 at 0:03

1 Answer 1

Reset to default
19
$\begingroup$

The best reference for relativized circuits is Chris Wilson's paper "Relativized NC" Link

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Aug 25, 2010 at 16:36
  • 3
    $\begingroup$ 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. $\endgroup$
    – Niel de Beaudrap
    Aug 25, 2010 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.