Позвольте быть любой полной проблемой EXP. Тогда Р = Н Р .
Пусть некоторый оракул , который принимает на счета запросов, М (а ТМ Р) будут делать, и мы можем получить P B ≠ N P B .
Вопрос: есть ли у нас аналогичные результаты оракула для P против BPP?
Ответы:
У меня было смутное воспоминание, что я знал превосходную ссылку для такого отделения оракула. Я наконец нашел это.
Отличным справочником по разделению оракулов (для классов между P и PSPACE) является следующая статья :
В статье показано (или приводится цитата) разделение оракула между почти каждой парой классов, которые могут вас беспокоить, между P и PSPACE (например, у него есть такие классы, как P, RP, BPP, UP, FewP, NP, MA, AM другие уровни PH, PH, IP, PSPACE и т. д.).
Например, теорема 8 показывает проблему оракула в coRP, которой нет в NP. Поскольку (относительно всех оракулов) coRP находится в BPP, а NP содержит P, мы получаем проблему оракула в BPP, которой нет в P.
источник
Сложность зоопарк является вашим другом! Как сказал Робин, у вас есть половина ответа: любая задача, полная EXP, сводит NP к P, и поэтому BPP к P. Buhrman и Fortnow создали оракула, относительно которого P = RP, но BPP не равен P. Это больше, чем что ты просил; Я подозреваю, что есть более простые конструкции, которые отделяют P от RP и BPP.
источник
Хорошее описание оракула, который разделяет P и BPP, дан Грегом Купербергом в одном из комментариев этого интересного поста в блоге , где Теренс Тао описывает машины Тьюринга с оракулами и результатами сложности относительно оракулов в форме аллегории.
источник
Беннетт и Джилл дают оракулы для обоих случаев: http://epubs.siam.org/doi/abs/10.1137/0210008
источник