Результаты Oracle на P против BPP

10

Позвольте быть любой полной проблемой EXP. Тогда Р = Н Р .APA=NPA

Пусть некоторый оракул , который принимает на счета запросов, М (а ТМ Р) будут делать, и мы можем получить P BN P B .BMPBNPB

Вопрос: есть ли у нас аналогичные результаты оракула для P против BPP?

Кава
источник
2
Да, мы делаем, но я не уверен, что смогу найти цитату. (Что ж, первая часть проста, дайте обоим классам оракула за задачу, полную опыта.)
Робин Котари
3
Если вы думаете о настройке PCP , как испытатель , имеющий доступ оракула к расстойкам (где запрос оракула возвратил бы я т ч немного доказательства) , то мы знаем , что если вы позволите верификатору быть машиной БПП с логом н хаотичностью и 3 запросов то класс языков вычисляется является Н Р и когда верификатор является Р машина (это не случайность) с 3 (даже с лог - п ) запросов , то класс языков , вычисленных является Р . Это не показывает разделение оракула , если только P N P . Но просто пример, где оракул доступ кiithlogn3NP3lognPPNP "кажется" более мощным. BPP
Саджин Корот
P=NP=EXPAEXPNPA=NPP=PP=P=NP=EXPPPA=NPAPP=NP=PPNP

Ответы:

13

У меня было смутное воспоминание, что я знал превосходную ссылку для такого отделения оракула. Я наконец нашел это.

Отличным справочником по разделению оракулов (для классов между P и PSPACE) является следующая статья :

Верещагин Н.К. (1994). "ОТНОСИТЕЛЬНЫЕ И НЕРЕЛЯТИВИЗИРУЕМЫЕ ТЕОРЕМЫ В ПОЛИНОМНОЙ ТЕОРИИ АЛГОРИТМОВ" РАН. Известия математики 42 (2): 261

В статье показано (или приводится цитата) разделение оракула между почти каждой парой классов, которые могут вас беспокоить, между P и PSPACE (например, у него есть такие классы, как P, RP, BPP, UP, FewP, NP, MA, AM другие уровни PH, PH, IP, PSPACE и т. д.).

Например, теорема 8 показывает проблему оракула в coRP, которой нет в NP. Поскольку (относительно всех оракулов) coRP находится в BPP, а NP содержит P, мы получаем проблему оракула в BPP, которой нет в P.

PA=BPPA

Робин Котари
источник
Вот ссылка на бесплатную загрузку с сайта citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232
Маркос Вильягра,
Хотя, если вы можете получить полную версию, я бы порекомендовал это вместо. В версии citeseer отсутствуют рисунки, и поэтому отсутствует хорошая диаграмма включения классов сложности (рис. 1).
Робин Котари
8

Сложность зоопарк является вашим другом! Как сказал Робин, у вас есть половина ответа: любая задача, полная EXP, сводит NP к P, и поэтому BPP к P. Buhrman и Fortnow создали оракула, относительно которого P = RP, но BPP не равен P. Это больше, чем что ты просил; Я подозреваю, что есть более простые конструкции, которые отделяют P от RP и BPP.

Сашо Николов
источник
6

Хорошее описание оракула, который разделяет P и BPP, дан Грегом Купербергом в одном из комментариев этого интересного поста в блоге , где Теренс Тао описывает машины Тьюринга с оракулами и результатами сложности относительно оракулов в форме аллегории.

Алессандро Косентино
источник
1
это классное описание :)
Сашо Николов
-1

Беннетт и Джилл дают оракулы для обоих случаев: http://epubs.siam.org/doi/abs/10.1137/0210008

Люк Мэтисон
источник
Они дают оракула, чтобы отделить BPP от P? Я не смог найти такое требование в газете.
Робин Котари
Я так и думал, к сожалению, я нахожусь вне своего офиса, поэтому у меня нет доступа к PDF. Я должен проверить позже.
Люк Мэтисон
BPPA=PA