<p>I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true.</p>

<p>First, is this a well-defined question? Are there any known results about the structure of such classes?</p>

<p>Second, is there an explicit problem in one of $\mathsf{NC}^{\mathsf{NP}}$, $\mathsf{NL}^{\mathsf{NP}}$, $\mathsf{FNC}^{\# \mathsf{P} }$, or $\mathsf{FNL}^{\# \mathsf{P}}$ and which is not in $\mathsf{P}$ under some assumption? After some research, I have not been able to find such a problem.</p>

CC BY-SA 3.0
2015-02-08T02:38:26.507Z
I don't understand your second question; isn't $\mathsf{SAT}$ an explicit problem in $\mathsf{NC}^\mathsf{NP}$ which is not in $\mathsf{P}$?
Ben Standeven
CC BY-SA 3.0
2014-08-15T01:35:38.030Z
You can start from Klaus Aehlig, Stephen Cook, Phuong Nguyen, "[Relativizing Small Complexity Classes and their Theories](http://arxiv.org/abs/1204.5508)", 2012.
Kaveh
CC BY-SA 3.0
2014-08-15T01:37:09.963Z
For your second question, $(\mathsf{AC}^0)^\mathsf{P} = \mathsf{P}$.
Kaveh
CC BY-SA 3.0
2014-08-19T14:27:50.790Z
A more interesting example (though still not answering your first question): $\mathsf{L}^{\mathsf{NP}} = \Theta^P_1 := \mathsf{P}^{\mathsf{NP}[\log n]}$.
Jan Johannsen
<cc.complexity-theory><complexity-classes>
How powerful are weak complexity classes with powerful oracles?
atsu
# How powerful are weak complexity classes with powerful oracles?

(Asked by: username_0 on 2014-08-15)

I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true.

First, is this a well-defined question? Are there any known results about the structure of such classes?

Second, is there an explicit problem in one of $\mathsf{NC}^{\mathsf{NP}}$, $\mathsf{NL}^{\mathsf{NP}}$, $\mathsf{FNC}^{\# \mathsf{P} }$, or $\mathsf{FNL}^{\# \mathsf{P}}$ and which is not in $\mathsf{P}$ under some assumption? After some research, I have not been able to find such a problem.

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_2**: You can start from Klaus Aehlig, Stephen Cook, Phuong Nguyen, "[Relativizing Small Complexity Classes and their Theories](http://arxiv.org/abs/1204.5508)", 2012.  
> **username_2**: For your second question, $(\mathsf{AC}^0)^\mathsf{P} = \mathsf{P}$.  
> **username_3**: A more interesting example (though still not answering your first question): $\mathsf{L}^{\mathsf{NP}} = \Theta^P_1 := \mathsf{P}^{\mathsf{NP}[\log n]}$.  
> **username_1**: I don't understand your second question; isn't $\mathsf{SAT}$ an explicit problem in $\mathsf{NC}^\mathsf{NP}$ which is not in $\mathsf{P}$?  

---

## 0 answers

