Для случайного оракула R равен ли BPP множеству вычислимых языков в P ^ R?

18

Ну, название в значительной степени говорит обо всем. Интересный вопрос выше задал комментатор Джей в моем блоге (см. Здесь и здесь ). Я предполагаю, что ответ - да, и что есть относительно простое доказательство, но я не мог видеть это наизусть. (Однако очень грубо можно попытаться показать, что если бы язык в отсутствовал в , то он должен иметь бесконечную алгоритмическую взаимную информацию с , и в этом случае он не был бы вычислим. Также обратите внимание, что одно направление тривиально: вычислимые языки в безусловно, содержат .)PRВппрпр Впп

Обратите внимание, что я не спрашиваю о классе NearP , который состоит из тех языков, которые есть в почти для каждого (и, как известно, он равен ). В этом вопросе мы сначала исправить , а затем посмотреть на множестве вычислимых языков в . С другой стороны, можно было бы попытаться показать , что, если язык в вычислим, даже для фиксированного случайного оракула , то в том , что язык должен быть в .пррВппрпрпррALмоsTп

С этим тесно связан вопрос: имеем ли мы с вероятностью 1 над случайным оракуломр

AMзнак равноNпрСомпUTaбLе,

Если это так, то мы получаем следующее интересное следствие: если , то с вероятностью 1 над случайным оракулом единственные языки, которые являются свидетелями разделения оракула являются невычислимыми языками.пзнак равноNпрпрNпр

Скотт Ааронсон
источник

Ответы:

16

Да.

Во-первых, поскольку мне потребовалась минута, чтобы понять это самостоятельно, позвольте мне формализовать разницу между вашим вопросом и ; это порядок квантификаторов. A l m o s t P : = { L : P r R ( L P R ) = 1 } , и результат, на который вы ссылаетесь, равен LALмоsTпALмоsTпзнак равно{L:прр(Lпр)знак равно1} . Если я правильно понял, вы спрашиваете, если P r R ( LLLВпппрр(Lпр)знак равно1 .PrR(LLпрСОMпLВпп)знак равнопрр(прСОMпзнак равноВпп)знак равно1

Рассмотреть возможность

.пзнак равно1-прр(прСОMпзнак равноВпп)знак равнопрр(LпрСОMпВпп)

По границе объединения ограничено сверху L C O M P P r R ( L P RB P P ) . (Обратите внимание, что последняя сумма является счетной.) Теперь по закону 0-1, который применяется, поскольку все соответствующие утверждения не меняются, если мы меняем R конечным образом, - каждая отдельная вероятность в этой сумме равна либо 0, либо 1. Если ответ на ваш вопрос - нет, тогда p = 1 , поэтому должно быть некоторое L C O M P такое, чтопΣLСОMппрр(LпрВпп)рp=1LCOMP . Но это противоречит томучто л м о с т Р = В Р Р .PrR(LPRBPP)=1AlmostP=BPP

Обновление 10 октября 2014 : Как было отмечено в комментарии Эмиль Jeřábek, тот же аргумент относится к против N P R , так как мы знаем , что л м о с т N P = M .AMNPRAlmostNP=AM

Он также указывает, что мы ничего не использовали в кроме того, что это счетный класс, содержащий B P P (соответственно, A M ). Таким образом, «интересный вывод» в OQ фактически применим к любому счетному классу языков C, который содержит A M : если P = N P , «единственные» языки, которые являются свидетелями разделения оракула P RN P R, находятся за пределами CCOMPBPPAMCAMP=NпPRNPRC, Но последнее утверждение кажется мне несколько вводящим в заблуждение (оно звучит так, как будто для любого мы могли бы рассмотреть C = A M{ L 0 } и тем самым «показать», что ни один L 0 не реализует N P RP R , противоречащему известной теореме). Скорее, написав это символически, мы показали:L0C=AM{L0} L0NPRPR

Если , то table счетное  CA MP=NP .countable CAMPrR(NPRPR and NPRC=PRC)=1

Следует отметить, что особенно важно, вероятность 1 это не то же самое, что все , и который полный набор мера R удовлетворяет аргумент P г R может зависеть от C . Так что, если мы попытаемся изменить C на C{ L 0 } , он в лучшем случае удалит множество R меры R, которые удовлетворяют этому утверждению.RRPrRCCC{L0}R

Джошуа Грохов
источник
5
Тот же аргумент применим к AM против NP ^ R. Кроме того, вычислимость на самом деле не имеет значения, единственное свойство вычислимых языков, используемых в доказательстве, состоит в том, что их насчитывается много.
Эмиль Йержабек поддерживает Монику
7

В то время как порядок квантификаторов между тем, что вы спрашиваете, и почти P различаются, нетрудно показать, что они эквивалентны. Во-первых, для любого фиксированного L вопрос о том, не зависит ли L \ in P ^ O от какого-либо конечного начального отрезка O., следует, что вероятность того, что L \ in P ^ R, равна 0 или 1. Из почти - В результате P, для каждого вычислимого L, не входящего в BPP, ответ равен 0, а если L \ в BPP, вероятность равна 1. Поскольку счетного L вычислимо много, мы можем сделать объединение; счетное объединение наборов вероятностей 0 имеет вероятность 0. Таким образом, вероятность того, что существует любой вычислимый L, который не находится в BPP, но находится в P ^ R, равна 0, так же как и вероятность того, что в BPP есть язык, не принадлежащий P ^ Р,

Рассел Импальяццо
источник