|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математические основы информатики и программирования
Релятивизованные генерические классы $\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}$ метод диагонализации также неприменим.
Ключевые слова:
генерическая сложность, проблема $\mathrm P=\mathrm{NP}$, оракулы.
Образец цитирования:
А. Н. Рыбалов, “Релятивизованные генерические классы $\mathrm P$ и $\mathrm{NP}$”, ПДМ, 2018, № 40, 100–104
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm622 https://www.mathnet.ru/rus/pdm/y2018/i2/p100
|
Статистика просмотров: |
Страница аннотации: | 150 | PDF полного текста: | 64 | Список литературы: | 24 |
|