$\begingroup$
$\endgroup$
6
The task is to show $A^{B}\subseteq C$, where, $A,\ B$ and $C$ are complexity classes.
Is (i) $A\subseteq C$, (ii) $B\subseteq C$ and, (iii) $B$=co-$B$ are sufficient conditions to deduce $A^{B}\subseteq C$?
Or is there a counter-example to it?
My motivation: the assumption $P^{NP}\subseteq NP$ implies NP=co-NP. I want to see if the converse holds true or not. And if it can be generalized to classes beyond P and NP.
asked Oct 28, 2024 at 9:30
Manish Kumar
2093 silver badges11 bronze badges
-
2$\begingroup$ $A^B$ is not an object uniquely defined from $A$ and $B$. Hence you cannot infer the inclusion you want from any property of $A$. $\endgroup$Emil Jeřábek– Emil Jeřábek2024年10月28日 12:21:06 +00:00Commented Oct 28, 2024 at 12:21
-
1$\begingroup$ $\mathrm{NP=coNP}$ does imply $\mathrm{P^{NP}=NP},ドル but because of more specific properties of these classes. $\endgroup$Emil Jeřábek– Emil Jeřábek2024年10月28日 12:28:59 +00:00Commented Oct 28, 2024 at 12:28
-
$\begingroup$ @EmilJeřábek, (as always) thanks! I tried building the generalization based on the intuition from the "special case" of P, NP, and $P^{NP}$. I will be happy if you can help me build a counter-example for the general case of A, B, and $A^{B}$. Thanks! $\endgroup$Manish Kumar– Manish Kumar2024年10月28日 14:55:00 +00:00Commented Oct 28, 2024 at 14:55
-
2$\begingroup$ As usual, these kind of things are very hard to construct. But let $X$ be an oracle such that $\mathrm P^X\ne\mathrm{NP}^X$; I think one can modify the usual proofs of their existence to show that, additionally, $X$ can be found with arbitrarily large complexity, in particular, we can assume $X$ is NP-hard. Put $A=\mathrm{NP}$ and $B=C=\mathrm P^X$. Then $A\subseteq C,ドル $B\subseteq C,ドル $B=\mathrm{co}B$ (even $B=\mathrm P^B$), but "$A^B$", i.e., $\mathrm{NP}^X,ドル is not included in $C$. $\endgroup$Emil Jeřábek– Emil Jeřábek2024年10月28日 15:28:43 +00:00Commented Oct 28, 2024 at 15:28
-
1$\begingroup$ But really, the question as formulated does not make sense. Once again: the notation $A^B$ has no meaning for arbitrary complexity classes $A$ and $B$. It is only defined when $A^{\dots}$ denotes a class of oracle Turing machines (or similar relativized devices), in which case $A^B$ is defined as the languages computed by such things when the oracle is taken from $B,ドル and the "class $A$" as such is defined as $A^\varnothing$. There is no general way of going in the opposite direction, from a complexity class $A$ to a class of relativized devices. $\endgroup$Emil Jeřábek– Emil Jeřábek2024年10月28日 15:32:53 +00:00Commented Oct 28, 2024 at 15:32