Ну, название в значительной степени говорит обо всем. Интересный вопрос выше задал комментатор Джей в моем блоге (см. Здесь и здесь ). Я предполагаю, что ответ - да, и что есть относительно простое доказательство, но я не мог видеть это наизусть. (Однако очень грубо можно попытаться показать, что если бы язык в отсутствовал в , то он должен иметь бесконечную алгоритмическую взаимную информацию с , и в этом случае он не был бы вычислим. Также обратите внимание, что одно направление тривиально: вычислимые языки в безусловно, содержат .)
Обратите внимание, что я не спрашиваю о классе NearP , который состоит из тех языков, которые есть в почти для каждого (и, как известно, он равен ). В этом вопросе мы сначала исправить , а затем посмотреть на множестве вычислимых языков в . С другой стороны, можно было бы попытаться показать , что, если язык в вычислим, даже для фиксированного случайного оракула , то в том , что язык должен быть в .
С этим тесно связан вопрос: имеем ли мы с вероятностью 1 над случайным оракулом
Если это так, то мы получаем следующее интересное следствие: если , то с вероятностью 1 над случайным оракулом единственные языки, которые являются свидетелями разделения оракула являются невычислимыми языками.
источник
Ответы:
Да.
Во-первых, поскольку мне потребовалась минута, чтобы понять это самостоятельно, позвольте мне формализовать разницу между вашим вопросом и ; это порядок квантификаторов. A l m o s t P : = { L : P r R ( L ∈ P R ) = 1 } , и результат, на который вы ссылаетесь, равен ∀ LA l m o s t P AlmostP:={L:PrR(L∈PR)=1} . Если я правильно понял, вы спрашиваете, если P r R ( ∀ L∀LL∈BPP⟺PrR(L∈PR)=1 .PrR(∀LL∈PR∩COMP⟺L∈BPP)=PrR(PR∩ C O M P = B P P ) =1
Рассмотреть возможность
.p:=1−PrR(PR∩COMP=BPP)=PrR(∃L∈PR∩COMP∖BPP)
По границе объединения ограничено сверху ∑ L ∈ C O M P P r R ( L ∈ P R ∖ B P P ) . (Обратите внимание, что последняя сумма является счетной.) Теперь по закону 0-1, который применяется, поскольку все соответствующие утверждения не меняются, если мы меняем R конечным образом, - каждая отдельная вероятность в этой сумме равна либо 0, либо 1. Если ответ на ваш вопрос - нет, тогда p = 1 , поэтому должно быть некоторое L ∈ C O M P такое, чтоp ∑L∈COMPPrR(L∈PR∖BPP) R p=1 L∈COMP . Но это противоречит томучто л м о с т Р = В Р Р .PrR(L∈PR∖BPP)=1 AlmostP=BPP
Обновление 10 октября 2014 : Как было отмечено в комментарии Эмиль Jeřábek, тот же аргумент относится к против N P R , так как мы знаем , что л м о с т N P = M .AM NPR AlmostNP=AM
Он также указывает, что мы ничего не использовали в кроме того, что это счетный класс, содержащий B P P (соответственно, A M ). Таким образом, «интересный вывод» в OQ фактически применим к любому счетному классу языков C, который содержит A M : если P = N P , «единственные» языки, которые являются свидетелями разделения оракула P R ≠ N P R, находятся за пределами CCOMP BPP AM C AM P=NP PR≠NPR C , Но последнее утверждение кажется мне несколько вводящим в заблуждение (оно звучит так, как будто для любого мы могли бы рассмотреть C = A M ∪ { L 0 } и тем самым «показать», что ни один L 0 не реализует N P R ≠ P R , противоречащему известной теореме). Скорее, написав это символически, мы показали:L0 C=AM∪{L0} L0 NPR≠PR
Если , то table счетное C ⊇ A MP=NP .∀countable C⊇AMPrR(NPR≠PR and NPR∩C=PR∩C)=1
Следует отметить, что особенно важно, вероятность 1 это не то же самое, что все , и который полный набор мера R удовлетворяет аргумент P г R может зависеть от C . Так что, если мы попытаемся изменить C на C ∪ { L 0 } , он в лучшем случае удалит множество R меры R, которые удовлетворяют этому утверждению.R R PrR C C C∪{L0} R
источник
В то время как порядок квантификаторов между тем, что вы спрашиваете, и почти 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 ^ Р,
источник