<p>I found an answer in Theorem 3 in <a href="http://www.cs.umbc.edu/~chang/papers/revisionist/rev-book.pdf" rel="noreferrer">Hartmanis, Chang, Chari, Ranjan, Rohatgi</a>. They show that relative to EXPSPACE-complete languages, PCP(log) = PCP(poly). Since PCP(log) = NP ≠ NEXP = PCP(poly), we are done.</p>

CC BY-SA 3.0
2010-08-26T07:47:22.907Z
2011-05-19T06:49:53.407Z
2011-05-19T06:49:53.407Z
manoj
<p><a href="http://doi.ieeecomputersociety.org/10.1109/CCC.1998.694585" rel="nofollow">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.</a> (also from <a href="http://www.cs.uchicago.edu/~fortnow/papers/nonrel.pdf" rel="nofollow">Lance's homepage</a>).  They show unconditionally that $MA_{EXP} \not\subseteq P/poly$, and also build an oracle relative to which $MA_{EXP} \subseteq P/poly$.</p>

CC BY-SA 2.5
2010-08-25T10:28:43.773Z
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?
manoj
CC BY-SA 2.5
2010-08-25T14:57:55.030Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-26T14:39:03.547Z
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.
Lance Fortnow
CC BY-SA 2.5
2010-08-24T21:05:46.863Z
2010-08-24T21:05:46.863Z
Joshua Grochow
<p>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.</p>

CC BY-SA 2.5
2010-08-25T10:30:37.380Z
Is there a reference for this? Your explanation was too fast for me.
manoj
CC BY-SA 2.5
2010-08-25T16:05:28.667Z
I believe the nondeterministic time hierarchy theorem is originally due to Cook (JCSS 7(4), pp. 343-353, 1973, http://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.  http://www.springerlink.com/content/v7740pn3q174p0u2/
Joshua Grochow
CC BY-SA 2.5
2010-08-24T18:25:36.370Z
2010-08-24T18:25:36.370Z
Joshua Grochow
<p>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.)</p>

<p>Similarly for NL and PSPACE. </p>

CC BY-SA 2.5
2010-08-25T01:45:34.487Z
There are some issues around how to relativize small-space bounded classes such as log-space.  See, for example, this question: http://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles.  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.
Joshua Grochow
CC BY-SA 2.5
2010-08-25T04:39:52.327Z
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.
Robin Kothari
CC BY-SA 2.5
2010-08-25T16:01:48.637Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-25T00:21:07.083Z
2010-08-25T00:21:07.083Z
Robin Kothari
<p>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$.</p>

CC BY-SA 2.5
2010-08-24T16:57:49.863Z
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?
Joshua Grochow
CC BY-SA 2.5
2010-08-24T18:13:24.720Z
Apologies if I am mistaken, but this reads like a homework question. Is it?
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-24T18:21:05.677Z
@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.)
Joshua Grochow
CC BY-SA 2.5
2010-08-25T10:21:17.553Z
Joshua: Thank you for adding the reference-request tag to the question. I accept your comment about oracle $B$ being unnecessary. 
Evgenij: Apology accepted :-)
manoj
<cc.complexity-theory><reference-request><complexity-classes><oracles>
Complexity class separation in the presence of relativization barriers
manoj
# Complexity class separation in the presence of relativization barriers

(Asked by: username_0 on 2010-08-24)

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$.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, oracles
> **Comments:**
> **username_1**: 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?  
> **username_2**: Apologies if I am mistaken, but this reads like a homework question. Is it?  
> **username_1**: @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.)  
> **username_0**: Joshua: Thank you for adding the reference-request tag to the question. I accept your comment about oracle $B$ being unnecessary.  Evgenij: Apology accepted :-)  

---

## 4 answers

### Answer by username_0 on 2010-08-26. Score: 7 | Accepted answer

I found an answer in Theorem 3 in [Hartmanis, Chang, Chari, Ranjan, Rohatgi](http://www.cs.umbc.edu/~chang/papers/revisionist/rev-book.pdf). They show that relative to EXPSPACE-complete languages, PCP(log) = PCP(poly). Since PCP(log) = NP ≠ NEXP = PCP(poly), we are done.


---

### Answer by username_1 on 2010-08-24. Score: 7

[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.](http://doi.ieeecomputersociety.org/10.1109/CCC.1998.694585) (also from [Lance's homepage](http://www.cs.uchicago.edu/~fortnow/papers/nonrel.pdf)). They show unconditionally that $MA\_{EXP} \not\subseteq P/poly$, and also build an oracle relative to which $MA\_{EXP} \subseteq P/poly$.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_3**: 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.  

---

### Answer by username_1 on 2010-08-24. Score: 4

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.

> **Comments:**
> **username_0**: Is there a reference for this? Your explanation was too fast for me.  
> **username_1**: I believe the nondeterministic time hierarchy theorem is originally due to Cook (JCSS 7(4), pp. 343-353, 1973, http://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.  http://www.springerlink.com/content/v7740pn3q174p0u2/  

---

### Answer by username_4 on 2010-08-25. Score: 3

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.

> **Comments:**
> **username_1**: There are some issues around how to relativize small-space bounded classes such as log-space.  See, for example, this question: http://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles.  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.  
> **username_4**: 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.  
> **username_1**: 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.  

---

