1
$\begingroup$

$NP\cap coNP$ is low for itself: $NP^{NP\cap coNP}\cap coNP^{NP\cap coNP}=NP\cap coNP$.

Going up to exponential realm, we are considering similarities of $NP\cap coNP$ to its exponential version $NEXP\cap coNEXP$.

By padding, we already have $$NEXP^{NP\cap coNP}\cap coNEXP^{NP\cap coNP}=NEXP\cap coNEXP$$

Two questions:

  1. Though it is unlikely, I do not know for sure whether $NEXP\cap coNEXP$ is low for itself: $$NEXP^{NEXP\cap coNEXP}\cap coNEXP^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$

  2. Being more moderate in using oracle machine, we may ask whether $$P^{NEXP\cap coNEXP}=NEXP\cap coNEXP$$

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. NO. Assume to the contrary that we have that equality, the LHS contains $EXP^{EXP}=EEXP$. So, we deduce that $NEXP=EEXP$.But then the LHS can even contain $EXP^{EEXP}=EEEXP$. That is way too much over $NEXP$.

  2. YES. By the same proof for $P^{NP\cap coNP}=NP\cap coNP$, the NEXP machine simulates the oracle machine by guessing the oracle answer and the corresponding certificate of membership (non-membership) and verify by the verifier (refuter, resp.) of the NEXP (coNEXP, resp.) machine for the language of the oracle. Then, if at any time the certuficate does not prove the guess, refute and halt. Otherwise, return the same answer as the oracle machine.

Similarly for the coNEXP machine, but you have to accept if a guess is not proven by the certificate guessed after it.

$\endgroup$

Your Answer

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