12
$\begingroup$

In a paper 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(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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nikhil
    Jun 14, 2012 at 4:51
3
$\begingroup$

In this paper https://people.cs.rutgers.edu/~allender/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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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