Wednesday, 2 June 2010

computability theory - 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 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:



A simple proof of NP != P ?



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