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.

  • 2
    $\begingroup$ It’s quite nontrivial to decide what is the right way to relativize $\mathrm{NC}^1$ in the first place. See in particular 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). $\endgroup$ – Emil Jeřábek Feb 7 at 14:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 7 at 14:41
  • $\begingroup$ Thanks for the clarification and references. $\endgroup$ – Abdallah Feb 8 at 2:45
  • $\begingroup$ Apologies that I asked too many basic questions in a row. I'll refrain from doing so in the future. $\endgroup$ – Abdallah Feb 8 at 2:46

Your Answer

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

Browse other questions tagged or ask your own question.