Why relativization can't solve NP !=P? - MathOverflow

Why relativization can't solve NP !=P?

2010-08-15T15:45:47Z

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?

Answer by ilyaraz for Why relativization can't solve NP !=P?

2010-08-15T16:02:20Z

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.

Answer by Akhil Mathew for Why relativization can't solve NP !=P?

2010-08-15T16:06:15Z

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

Answer by Joel David Hamkins for Why relativization can't solve NP !=P?

2010-08-15T17:16:36Z

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.

Answer by Suresh Venkat for Why relativization can't solve NP !=P?

2010-08-15T18:11:29Z

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.