## Why relativization can’t solve NP !=P?

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?

-

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

-
+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 2010 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! – Sid Aug 16 2010 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. people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.ps – Suresh Venkat Aug 16 2010 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 2010 at 0:36

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.

-
Here's a reference: portal.acm.org/citation.cfm?id=49327 This paper shows that co-NP does not have interactive proofs. – Suresh Venkat Aug 15 2010 at 16:23
Doesn't that contradict co-NP $\subseteq$ PSPACE = IP ? – Ricky Demer Aug 15 2010 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. – Sid Aug 15 2010 at 19:00
Then Suresh should have said ""co-NP has interactive proofs" does not relativize". – Ricky Demer Aug 15 2010 at 19:08
my mistake. Ricky is indeed correct. – Suresh Venkat Aug 16 2010 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.

-

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.

-
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 2010 at 5:38