MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited tags
1

# 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?