0
$\begingroup$

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
$\endgroup$
6
  • 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Oct 28, 2024 at 15:32

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.