Where can I learn more about relativisations of P and NP?
A landmark paper entitled "Relativisations of the P =? NP Question" by Theodore Baker, John Gill, and Robert Solovay was published in the SIAM Journal of Computing Vol.4, No.4, December 1975.
It talks about the P vs. NP problem and introduces methods of relativisations. I have the paper, but I'd like to know more about testing an algorithm to see if it is relativisable. Where can I find more resources on this?
There is more information. A recent attempt was made at proving that P is not equal to NP, and it involved trying to avoid relativisations. I was wondering if someone might have more information on this so that I may be able to learn more on the techniques involved. For example, a link to the paper would be good.
Again, any help on this topic would be greatly ap开发者_StackOverflowpreciated.
I found this blog (from Terry Tao) interesting on the subject.
精彩评论