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:
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?
No comments:
Post a Comment