1
$\begingroup$

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively.

  1. Then is it always true $X^Z\subseteq Y^Z$ if $Z$ is another complexity class?

  2. If not what is an easy way and example to understand $X^Z\subseteq Y^Z$ need not be true?

$\endgroup$
14
  • 2
    $\begingroup$ How do you define $X^Z$ in general? What do you mean by a "complexity class in the polynomial hierarchy"? $\endgroup$ – Yuval Filmus Jun 2 '17 at 10:04
  • 2
    $\begingroup$ This is not enough. What are $X,Y$? If you treat them as a set of languages, then it is not clear what "using Z" means, so they need to be defined with regard to some type of bounded resources machine. $\endgroup$ – Ariel Jun 2 '17 at 10:29
  • 1
    $\begingroup$ Things also depend on what Zs you allow as ​ "another complexity class" . ​ ​ ​ Allowing ​ "problems logspace reducible to S" ​ is at least as general ​ ​ ​ ​ ​ ​ ​ (... continued) ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jun 2 '17 at 11:01
  • 1
    $\begingroup$ (continued ...) ​ ​ ​ ​ ​ ​ ​ as allowing just an oracle for the language S, in which case one can get ​ ​ ​ TALLY $\cap$ coUP$^{\hspace{.02 in}Z} \: \not\subseteq \: $ IP$^{\hspace{.02 in}Z} \:$, ​ ​ ​ even though ​ P $\subseteq$ coUP $\subseteq$ PSPACE = IP . ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Jun 2 '17 at 11:01
  • 1
    $\begingroup$ Perhaps this question might clear some issues cs.stackexchange.com/questions/37626/… $\endgroup$ – Ariel Jun 2 '17 at 12:06

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.