MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.

When I learnt to the topic of relativization and oracle machines, I read the following theorem:

There exist oracles A, B such that $P^A = NP^A$ and $P^B \neq NP^B$.

And then the book said because of this, we can't solve the problem of NP = P by using relativization. But I think what it implies is that $NP \neq P$. The reasoning is like this:

First of all, it is quite easy to see that:

$$A = B \Leftrightarrow \forall \text{oracle O, }A^O = B^O$$

Though I think it is obvious, I still give a proof to it:

A simple proof of NP != P ?

And the negation of it is:

$$A \neq B \Leftrightarrow \exists \text{oracle O such that } A^O \neq B^O$$

Therefore since there is an oracle B such that:

$$ NP^B \neq P^B$$

we can conclude that $ NP \neq P $

What's the problem with the above reasoning?

share|cite|improve this question
up vote 19 down vote accepted

The map $A \to A^O$ does not depend only on the elements contained in the language $O$, so it is not an operation on languages. It depends on the semantic way in which the language $A$ is defined. For instance, $NP^O$ is allowed both nondeterminism and access to $O$. $P^O$ is allowed deterministic polynomial time and access to $O$. I believe it is true that $BPP$ can be separated from $P$, even though it is thought that $BPP = P$.

share|cite|improve this answer
+1. Akhil, I think this is exactly right. The notion of $\Gamma^O$ for an arbitrary class $\Gamma$ of languages seems to be incoherent. – Joel David Hamkins Aug 15 '10 at 22:56
I'm confused by your last sentence since I can't fit it with the rest of your reply. Given that it talks about relativisation, do you mean that BPP can be separated from P given some oracle? Thanks! – Opt Aug 16 '10 at 2:38
Correct. This is the reference from the Complexity zoo: [BF99] H. Buhrman and L. Fortnow. One-sided versus two-sided randomness, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 100-109, 1999. – Suresh Venkat Aug 16 '10 at 6:26
Yes, and it gets worse. When you move to relativizations of space-bounded complexity classes, there are multiple possible ways of defining oracle access: do we allow the oracle tape to be write-only so that queries can exceed the space bound, or not? The choice affects what you can separate and collapse using oracles. A sampling of these headaches can be found in Ruzzo, Simon, Tompa: "Space-Bounded Hierarchies and Probabilistic Computations" (1984) and papers that cite them. This is one reason why it's unclear what relativization barriers say about space lower bounds. – Ryan Williams Aug 18 '10 at 0:36
Yes, I forever lament (and I think many others do too) that the notation for oracles in complexity theory is very broken and confusing. (Ilya gives the canonical example of this, regarding IP and PSPACE.) As others are saying here, you actually define oracles relative to a machine class (i.e., model of computation), not relative to languages or complexity classes. Let's not even get started on the meaning of relativization with respect to promise problems... – Ryan O'Donnell Dec 19 '14 at 8:50

The statement $A = B \rightarrow \forall O \; A^O = B^O$ is incorrect. For example, it is known that $\mathrm{IP} = \mathrm{PSPACE}$, but we know that there exists an oracle $A$ such that $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$.

Direct substituion does not work here, because different characterisations of one particular class can behave different when we relativize them.

share|cite|improve this answer
Here's a reference: This paper shows that co-NP does not have interactive proofs. – Suresh Venkat Aug 15 '10 at 16:23
Doesn't that contradict co-NP $\subseteq$ PSPACE = IP ? – Ricky Demer Aug 15 '10 at 18:38
@Ricky - The abstract states that there exists an oracle relative to which co-NP does not have interactive proofs. Since IP^A \neq PSPACE ^A for some oracle A, everything works out. – Opt Aug 15 '10 at 19:00
Then Suresh should have said ""co-NP has interactive proofs" does not relativize". – Ricky Demer Aug 15 '10 at 19:08
my mistake. Ricky is indeed correct. – Suresh Venkat Aug 16 '10 at 6:28

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is that since all the standard methods do admit relativization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle.

That is, the point isn't that the theorem rules out the one method of relativization as a method of solving P versus NP, but rather that it rules out all methods that accommodate relativization. Since this includes most of our methods, it is a serious obstacle.

share|cite|improve this answer

I was holding off on posting a non-answer, but am encouraged by JDH.

There's still something deeply puzzling about the idea that if $A = B$, there's possibly an oracle for which $A^O \ne B^O$, and that seems to be at the heart of the OP question. In that respect, ilyaraj's example of IP and PSPACE is actually better, because unlike with P and NP, where we don't know the true answer, we actually KNOW that IP = PSPACE, and yet there's still an oracle that separates them.

But I think a deeper explanation needs to go beyond relativization, to the properties that relativization relies on. The Arora-Barak book explains this quite well: they point out that proofs like diagonalization rely on efficient simulation (universality) and the ability to list out machines (enumeration), and that any oracle-based result relies ONLY on these two properties.

Thus, the real answer to why P vs NP is independent of relativized arguments is that you need to exploit more information than just universality and enumeration. This comes to mind precisely because of the "new" barrier coming out the Deolalikar proof discussions, that proof techniques that try to differentiate the geometry of solutions to SAT vs P-time problems can't work.

share|cite|improve this answer
My 2 cents: The way I think of the this is that although A and B are equal, they might have different oracle access mechanisms. If A is allowed to interact with an oracle in a weak way while B can interact in a very powerful way, then it is reasonable that A^O cannot solve all the problems that B^O can, since O is not helping A as much as it is helping B. – Robin Kothari Aug 16 '10 at 5:38

And of course, this is exactly what happens in the $\mathrm{IP}^A \ne \mathrm{PSPACE}^A$ proof -- IP is defined by its access to outside information, which can be considered akin to an oracle -- while PSPACE does not. In the most cursory sense, both the IP-verifier and the IP-prover have access to an oracle of random bits. PSPACE-bound machines in general do not. A cursory way of looking at this, without even reference to the proof (which frankly I forget) is that granting IP an oracle of random bits would by definition do noting to it. But granting PSPACE an oracle of random bits could improve its computational ability.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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