2
$\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?

Improve this question
$\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, 2017 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, 2017 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, 2017 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, 2017 at 11:01
  • 1
    $\begingroup$ Perhaps this question might clear some issues cs.stackexchange.com/questions/37626/… $\endgroup$
    – Ariel
    Jun 2, 2017 at 12:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.