Релятивизованные генерические классы $\mathrm P$ и $\mathrm{NP}$

Бейкер, Гилл и Соловей в 1975 г. построили такие два оракула $A$ и $B$, что $\mathrm P^A=\mathrm{NP}^A$, но $\mathrm P^B\neq\mathrm{NP}^B$. Тем самым они показали, что неравенство $\mathrm P\neq\mathrm{NP}$ не может быть доказано с использованием метода диагонализации. В рамках генерического подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве “почти всех' входов. Такие входы образуют так называемое генерическое множество. Понятие "почти все” формализуется введением естественной меры на множестве входных данных. В работе определяются генерические аналоги $\mathrm{genP}$ и $\mathrm{genNP}$ классов вычислительной сложности $\mathrm P$ и $\mathrm{NP}$, а также их релятивизованные версии. Доказывается генерический аналог теоремы Бейкера–Гилла–Соловея: существуют такие оракулы $A$ и $B$, что $\mathrm{genP}^A=\mathrm{genNP}^A$, но $\mathrm{genP}^B\neq\mathrm{genNP}^B$. Таким образом, для решения генерического аналога проблемы совпадения классов $\mathrm P$ и $\mathrm{NP}$ метод диагонализации также неприменим.