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 PA=NPA and PBneqNPB.
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 NPneqP. The reasoning is like this:
First of all, it is quite easy to see that:
A=BLeftrightarrowforalltextoracleO,AO=BO
Though I think it is obvious, I still give a proof to it:
And the negation of it is:
AneqBLeftrightarrowexiststextoracleOsuchthatAOneqBO
Therefore since there is an oracle B such that:
NPBneqPB
we can conclude that NPneqP
What's the problem with the above reasoning?
No comments:
Post a Comment