开发者

Where can I learn more about relativisations of P and NP?

开发者 https://www.devze.com 2023-01-14 15:18 出处:网络
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.

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.

0

精彩评论

暂无评论...
验证码 换一张
取 消