Релятивизованные генерические классы Р и NP | Прикладная дискретная математика. 2018. № 40. DOI: 10.17223/20710410/40/8

Бейкер, Гилл и Соловей в 1975 г. построили такие два оракула А и В, что Р"⁴ = NP"⁴, но Р^Б ф NP^S. Тем самым они показали, что неравенство Р ф NP не может быть доказано с использованием метода диагонализации. В рамках ге-нерического подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. В работе определяются генерические аналоги genP и genNP классов вычислительной сложности Р и NP, а также их релятивизованные версии. Доказывается генерический аналог теоремы Бейкера - Гилла - Соловея: существуют такие оракулы А и В, что genP"⁴ = genNP"⁴, но genP⁵ ф genNP⁵. Таким образом, для решения гене-рического аналога проблемы совпадения классов Р и NP метод диагонализации также неприменим.