<p>A few things are known about the class <span class="math-container">$\textsf{L}$</span> provided with an <span class="math-container">$\textsf{NP}$</span> oracle (<span class="math-container">$\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$</span> has attracted a bit of attention, for instance [1]) On the other hand, I can't find much about the class <span class="math-container">$\textsf{NC}^1$</span> with access to an <span class="math-container">$\textsf{NP}$</span> oracle. Is it because the use of an oracle doesn't play well with the definition of <span class="math-container">$\textsf{NC}^1$</span>? Which I doubt. Most likely, it's because I haven't looked properly.</p>
<p>Except for the direct <span class="math-container">$\textsf{NP} \cup \textsf{coNP} \subseteq {\textsf{NC}^1}^{\textsf{NP}} \subseteq \Theta_2^{\textsf{P}}$</span>, What is known about <span class="math-container">${\textsf{NC}^1}^{\textsf{NP}}$</span>?</p>
<p>[1] <a href="https://doi.org/10.1007/3-540-19488-6_150" rel="nofollow noreferrer">Wagner, K. W. (1988, July). On restricting the access to an NP-oracle. In International Colloquium on Automata, Languages, and Programming (pp. 682-696). Springer, Berlin, Heidelberg.</a></p>

CC BY-SA 4.0
2021-02-07T14:30:11.603Z
It’s quite nontrivial to decide what is the right way to relativize $\mathrm{NC}^1$ in the first place. See in particular https://arxiv.org/abs/1204.5508. But any sensible definition should make $\mathrm{NC^{1\,NP}}$ the same as $\Theta^P_2$, as already $\mathrm{AC^{0\,NP}}$ does that (this follows from the representation of $\Theta^P_2$ as in Theorem 4 of [Buss & Hay](https://math.ucsd.edu/~sbuss/ResearchWeb/ttreduce/index.html)).
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T14:41:02.127Z
These are not quite research-level questions. I think you should slow down on question asking, and instead study the basic literature on $\Theta^P_2$ first.
Emil Jeřábek
CC BY-SA 4.0
2021-02-08T02:45:30.147Z
Thanks for the clarification and references.
Abdallah
CC BY-SA 4.0
2021-02-08T02:46:15.667Z
Apologies that I asked too many basic questions in a row. I'll refrain from doing so in the future.
Abdallah
CC BY-SA 4.0
2022-12-29T18:37:30.313Z
How deep does the oracle takes? If it take 1 layer then it'd be used as a high fan-in gate
l4m2
<complexity-classes><circuit-complexity><oracles>
Is anything known about NC$^1$ with NP oracle
Abdallah
# Is anything known about NC$^1$ with NP oracle

(Asked by: username_0 on 2021-02-07)

A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta\_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the other hand, I can't find much about the class $\textsf{NC}^1$ with access to an $\textsf{NP}$ oracle. Is it because the use of an oracle doesn't play well with the definition of $\textsf{NC}^1$? Which I doubt. Most likely, it's because I haven't looked properly.

Except for the direct $\textsf{NP} \cup \textsf{coNP} \subseteq {\textsf{NC}^1}^{\textsf{NP}} \subseteq \Theta\_2^{\textsf{P}}$, What is known about ${\textsf{NC}^1}^{\textsf{NP}}$?

[1] [Wagner, K. W. (1988, July). On restricting the access to an NP-oracle. In International Colloquium on Automata, Languages, and Programming (pp. 682-696). Springer, Berlin, Heidelberg.](https://doi.org/10.1007/3-540-19488-6_150)

**Tags:** complexity-classes, circuit-complexity, oracles
> **Comments:**
> **username_1**: It’s quite nontrivial to decide what is the right way to relativize $\mathrm{NC}^1$ in the first place. See in particular https://arxiv.org/abs/1204.5508. But any sensible definition should make $\mathrm{NC^{1\,NP}}$ the same as $\Theta^P_2$, as already $\mathrm{AC^{0\,NP}}$ does that (this follows from the representation of $\Theta^P_2$ as in Theorem 4 of [Buss & Hay](https://math.ucsd.edu/~sbuss/ResearchWeb/ttreduce/index.html)).  
> **username_1**: These are not quite research-level questions. I think you should slow down on question asking, and instead study the basic literature on $\Theta^P_2$ first.  
> **username_0**: Thanks for the clarification and references.  
> **username_0**: Apologies that I asked too many basic questions in a row. I'll refrain from doing so in the future.  
> **username_2**: How deep does the oracle takes? If it take 1 layer then it'd be used as a high fan-in gate  

---

## 0 answers

