|
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:
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 First of all, it is quite easy to see that:
Though I think it is obvious, I still give a proof to it: And the negation of it is:
Therefore since there is an oracle B such that:
we can conclude that What's the problem with the above reasoning?
|
||||

