Знаковым документ, озаглавленный «Relativisations о P =? NP Вопрос» Теодор Бейкер, Джон Гилл и Роберт Соловеем был опубликован в журнале SIAM вычислительной Vol.4, № 4, декабрь 1975 г.Где я могу узнать больше о релятивизациях P и NP?
Это рассказывает о проблеме P против NP и вводит методы релятивизации. У меня есть бумага, но я хотел бы узнать больше о тестировании алгоритма, чтобы узнать, является ли он релятивизируемым. Где я могу найти больше ресурсов на этом?
Дополнительная информация. Недавняя попытка была сделана при доказательстве того, что Р не равен NP, и в нем участвуют попытки избежать релятивизаций. Мне было интересно, может ли кто-нибудь получить дополнительную информацию об этом, чтобы я мог больше узнать о тех приемах. Например, ссылка на бумагу была бы хорошей.
С другой стороны, любая помощь по этой теме будет принята с благодарностью.
Интересный и полезный вопрос, но для меня это выглядит так, как будто это будет больше дома в http://cstheory.stackexchange.com/ – MAK