7
$\begingroup$

Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that 1. $M^A=N^A$ and 2. $M^B\neq N^B$ and 3. $M \neq N$.

$\endgroup$
  • 6
    $\begingroup$ The oracle $B$ is unnecessary here: since, by (3) $M \neq N$, we can take $B$ to be the empty oracle. Essentially what you're asking is: do we know of any complexity class separations (as opposed to collapses) that do not relativize? $\endgroup$ – Joshua Grochow Aug 24 '10 at 16:57
  • 2
    $\begingroup$ Apologies if I am mistaken, but this reads like a homework question. Is it? $\endgroup$ – Evgenij Thorstensen Aug 24 '10 at 18:13
  • 5
    $\begingroup$ @Evgenij: No, it is more of a reference request. The reason it is not a homework question is that manoj is asking for classes $M$ and $N$ where we know, unconditionally that $M \neq N$. He's not asking for a diagonalization construction on the spot or anything like that. (I admit though, the first time I read the question cursorily I had the same reaction.) $\endgroup$ – Joshua Grochow Aug 24 '10 at 18:21
  • $\begingroup$ Joshua: Thank you for adding the reference-request tag to the question. I accept your comment about oracle $B$ being unnecessary. Evgenij: Apology accepted :-) $\endgroup$ – manoj Aug 25 '10 at 10:21
7
$\begingroup$

H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 8-12. IEEE, New York, 1998. (also from Lance's homepage). They show unconditionally that $MA_{EXP} \not\subseteq P/poly$, and also build an oracle relative to which $MA_{EXP} \subseteq P/poly$.

$\endgroup$
  • $\begingroup$ Thanks, Joshua. I am going through the paper. Correct me if I'm wrong, but prima facie it appears as if this will not answer my question since $P/poly\notsubseteq MA_{EXP}$. Perhaps one can consider some non-uniform version of $MA_{EXP}$ that contains $P/poly$, but then will the separation result hold? $\endgroup$ – manoj Aug 25 '10 at 10:28
  • $\begingroup$ Strictly speaking you are correct: relative to the oracle they only get containment one way. However, with two classes neither of which is contained in the other, showing that one is not contained in the other is typically considered a separation and showing that one is contained in the other is typically considered a collapse. So although it does not answer the question to the letter, I think it answers the spirit of the question (a separation that does not relativize). I do not know of any examples that answer your question to the letter. $\endgroup$ – Joshua Grochow Aug 25 '10 at 14:57
  • 1
    $\begingroup$ Manoj has the right idea. Relative to our oracle MA_EXP/poly is in P/poly just by concatenating the advice strings. P/poly is in MA_EXP/poly for all oracles. The non-relativized separation of MA_EXP/poly from P/poly holds since MA_EXP is contained in MA_EXP/poly. $\endgroup$ – Lance Fortnow Aug 26 '10 at 14:39
6
$\begingroup$

I found an answer in Theorem 3 in Hartmanis, Chang, Chari, Ranjan, Rohatgi. They show that relative to EXPSPACE-complete languages, PCP(log) = PCP(poly). Since PCP(log) = NP ≠ NEXP = PCP(poly), we are done.

$\endgroup$
4
$\begingroup$

Here's one that almost doesn't relativize. $NEXP$ is not contained in $NP$ by the nondeterministic time hierarchy theorem. But one can construct, relatively easily, an oracle in which $NEXP$ is infinitely-often contained in $NP$. Formally, this means that there is an oracle relative to which there is a $NEXP$-complete problem $X$ such that $X$ agrees with (the relativized version of) $SAT$ infinitely often.

$\endgroup$
  • $\begingroup$ Is there a reference for this? Your explanation was too fast for me. $\endgroup$ – manoj Aug 25 '10 at 10:30
  • $\begingroup$ I believe the nondeterministic time hierarchy theorem is originally due to Cook (JCSS 7(4), pp. 343-353, 1973, dx.doi.org/10.1016/S0022-0000(73)80028-5). The oracle result can be found in: Harry Buhrman, Lance Fortnow and Rahul Santhanam. Unconditional Lower Bounds against Advice. ICALP 2009, Springer Lecture Notes in CS 5555. springerlink.com/content/v7740pn3q174p0u2 $\endgroup$ – Joshua Grochow Aug 25 '10 at 16:05
3
$\begingroup$

How about L and PSPACE. They are unequal because of the space hierarchy theorem. However, with oracle access to the language TQBF, which is PSPACE-hard under log space reductions, they become equally powerful. (Both equal PSPACE.)

Similarly for NL and PSPACE.

$\endgroup$
  • 1
    $\begingroup$ There are some issues around how to relativize small-space bounded classes such as log-space. See, for example, this question: cstheory.stackexchange.com/questions/7/…. In particular, since the proof is essentially the same as the proof of the time hierarchy theorem (for which there are no issues about the definition of relativization), I would say that the proof of the space hierarchy theorem doesn't really bypass the relativization barrier. $\endgroup$ – Joshua Grochow Aug 25 '10 at 1:45
  • 1
    $\begingroup$ I thought that $L^X$ should at least include all the problems reducible to $X$ via log space reductions. But I don't know much about relativizing small space-bounded classes, so perhaps my example is incorrect. $\endgroup$ – Robin Kothari Aug 25 '10 at 4:39
  • 2
    $\begingroup$ In principle I agree that $L^X$ should include all problems that are log-space reducible to $X$. One problem is that, with the notion of relativization we're using, there are oracles relative to which $NL \not\subseteq P$, which I don't agree with in principle (i.e. in principle that proof should relativize). Also, I still stand by the fact that the standard hierarchy theorems should in principle not count as examples of non-relativizing separations. So, my principles conflict :), but such is the tricky nature of relativizing small-space bounded classes, I guess. $\endgroup$ – Joshua Grochow Aug 25 '10 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.