Может ли случайный оракул изменить, какие проблемы с TFNP сильно усугубляются?

9

Я думал о следующем вопросе в
разное время с тех пор, как увидел этот вопрос по криптографии .


Вопрос

Позволять Rбыть отношением TFNP . Может ли случайный оракул помочь П / поли
сломаться?Rс ничтожной вероятностью? Более формально,

Имеет ли

для всех P / поли алгоритмовA, Prx[R(x,A(x))]является незначительным

обязательно подразумевают, что

для почти всех O racles O, Для всех P / поли оракула-алгоритмы A,Prx[R(x,AO(x))]Ничтожно мал

?


Альтернативная формулировка

Соответствующий набор оракулов Gδσ(таким образом измеримым), поэтому, принимая контраположительное и применяя закон Колмогорова ноль один , следующая формулировка эквивалентна исходной.

Имеет ли

для почти всех O racles O,
существует P / poly oracle-алгоритмA такой, что Prx[R(x,AO(x))]не пренебрежимо мало

обязательно подразумевают, что

существует алгоритм P / poly A такой, что Prx[R(x,A(x))] не пренебрежимо мало

?


Единый корпус

Вот доказательство для единой версии :

Существует только многочисленное множество алгоритмов оракула PPT, поэтому из-за исчисляемой аддитивности нулевого [идеального] [8] есть алгоритм PPT Aтакой, что для ненулевого набора оракуловO,
Prx[R(x,AO(x))]не является ничтожным ПозволятьB будь таким оракулом-алгоритмом.

Точно так же, пусть c быть положительным целым числом таким, чтобы для ненулевого набора оракулов O,
Prx[R(x,BO(x))] бесконечно часто, по крайней мере, nc, где nдлина ввода.
Противоположным Борел-Кантелли , n=0PrO[ncPrx{0,1}n[R(x,BO(x))]] бесконечен.

По сравнительному тесту , бесконечно часто PrO[ncPrx{0,1}n[R(x,BO(x))]n2,

Позволять S быть алгоритмом PPT, который [имитирует оракула] [12] и работает B с этим смоделированным оракулом.

Fix n и разреши Good быть набором оракулов O такой, что ncPrx{0,1}n[R(x,BO(x))],

Если Good тогда не нуль

PrO[OGood]nc=PrO[OGood]EO[nc]PrO[OGood]EO[Prx{0,1}n[R(x,BO(x))]OGood]=EO[Prx{0,1}n[OGood and R(x,BO(x))]]EO[Prx{0,1}n[R(x,BO(x))]]=PrO,x{0,1}n[R(x,BO(x))]=Prx{0,1}n,O[R(x,BO(x))]=Ex{0,1}n[PrO[R(x,BO(x))]]=Ex{0,1}n[Pr[R(x,S(x))]]=Prx{0,1}n[R(x,S(x))]
,

поскольку PrO[OGood]n2 бесконечно часто, Prx[R(x,S(x))] не является незначительным.

Поэтому единый вариант верен. В доказательстве критически используется тот факт, что существует
только много счетных алгоритмов PPT . Эта идея не работает в
неоднородном случае, так как существует множество континуальных алгоритмов P / poly oracle.

Сообщество
источник
Я не думаю, что это действительно вопрос о оракулах. посколькуO не зависит от RВы можете также дать Aдоступ к случайной строке. Тогда возникает вопрос: увеличивает ли случайность мощность многоразмерных цепей? Ответ на это "нет", так как еслиA Если бы вы получили доступ к случайной строке, то, используя аргумент усреднения, существует особая настройка случайной строки, с которой A могли бы сделать хорошо, и тогда мы могли бы просто закрепить эту строку в AСхема
Адам Смит
@AdamSmith: "С O не зависит от RВы можете также дать AДоступ к случайной строке»есть интуиция, но я не вижу какой - либо способ превратить его в доказательство.
1
@ Адам, есть еще один важный показатель. Я думаю, что легче взглянуть на отрицание: возможно ли, что почти для каждого оракула существует неоднородный противник, который может использовать оракула для решения проблемы поиска?
Каве
Понимаю. Я отвечал на другой вопрос. Извините за путаницу.
Адам Смит
@domotorp: они должны быть исправлены сейчас. (Моя лучшая догадка, почему это произошлоиспользование пронумерованных ссылок , а не в линии связи).

Ответы:

0

Нет моему названию и Да моему телу вопроса. Это фактически обобщает сразу
для каждой игры полиномиальной длины, которая не использует код противника.


Обратите внимание, что я буду использовать C для противников, а не A,
чтобы соответствовать обозначениям теоремы 2 .

Предположим, что почти для всех оракулов O, существует P / poly
oracle-алгоритмC такой, что Prx[R(x,CO(x))] не является ничтожным


Почти для всех оракулов Oсуществует такое положительное целое число d, что
существует последовательность цепей размером не более d + n d, такая что
Prx{0,1}n[R(x,CO(x))] бесконечно часто больше, чем 1/(nd),

По счетной аддитивности существует такое положительное целое число d, что для ненулевого набора оракулов Oсуществует последовательность цепей размером не более d + n d такая, что
Prx{0,1}n[R(x,CO(x))] бесконечно часто больше, чем 1/(nd),

Пусть j будет таким объявлением, и пусть z будет (не обязательно эффективным) алгоритмом оракула, который
принимает n в качестве входных данных и выводит лексикографически наименьшую схему оракула размером не более j + nj
что максимизирует Prx{0,1}n[R(x,CO(x))], Противоположным Борел-Кантелли ,1/(n2)<ProbO[1/(nj)<Prx{0,1}n[R(x,(zO)O(x))]]для бесконечно многих п.


Для таких n,

1/(n2+j)=1/((n2)(nj))=(1/(n2))(1/(nj))<ProbO,x{0,1}n[R(x,(zO)O(x))]

,


ПозволятьA быть оракулом-алгоритмом, который принимает 2 входа, один из которых nи делает следующее:

Выберите случайную n-битную строку x, Попытайтесь
[проанализировать другой вход как цепь оракула и запустить эту схему оракула на n-битной строке].
Если это удастся и вывод оракулаyудовлетворяет R (x, y), затем выдает 1, иначе выдает 0.


(Обратите внимание, чтоAэто не только противник.)
Для бесконечно многих п,1/(n2+j)<ProbO[AO(n,zO(n))],
Пусть p будет таким же, как в теореме 2 , и положимf=2p(j+nj)n(2+j)2,


По теореме 2 существует функция оракулаS такой, что с Pкак в этой теореме,
если1/(n2+j)<ProbO[AO(n,zO(n))] тогда

1/(2(n2+j))=(1/(n2+j))(1/(2(n2+j)))=(1/(n2+j))1/(22(n(2+j)2))
=(1/(n2+j))(p(j+nj))/(22p(j+nj)(n(2+j)2))=(1/(n2+j))(p(j+nj))/(2f)
<ProbO[AO(n,zO(n))](p(j+nj))/(2f)ProbO[AP(n,zO(n))],


Для такого, что1/(n2+j)<ProbO[AO(n,zO(n))]:

В частности, существует [оракул C размером не более j + nj] а также
[назначение длины не более f] такой, что с этим входом и предварительной выборкой,
Aвероятность вывода 1 больше, чем 1/(2(n2+j)),
Oracle-схемы размером не более j + njможет быть представлен битами poly (n), поэтому для p ограничен
сверху полиномом от n, что означает, что f также ограничен сверху полиномом от n.
По построениюAэто означает, что существуют схемы оракула размером не более j + njи назначение
длины полинома таким образом, чтобы при запуске с этой предварительной дискретизацией вероятность нахождения решения цепями была больше, чем1/(2(n2+j)), Поскольку такие схемы не могут делать запросы длиннее, чем j + njбиты, предварительно выбранные входы длиннее, чем это, можно игнорировать, поэтому такая предварительная выборка может эффективно и безошибочно моделироваться случайным оракулом и поли (n) жестко закодированными битами. Это означает, что существуют схемы оракула полиномиального размера, так что при стандартном случайном оракуле вероятность того, что схемы найдут решение, больше1/(2(n2+j)), Такой случайный оракул в свою очередь может быть эффективно-и-отлично моделируется только с обычными случайными битами, поэтому существует полиномиального размера вероятностные не являющиеся схемы -oracle, вероятность нахождения решения больше1/(2(n2+j)), В свою очередь, с помощью жесткого кодирования оптической случайности существуют детерминированные (неракулярные) схемы полиномиального размера, вероятность (из-за выбора x) которых может найти решение больше, чем1/(2(n2+j)),


Как показано ранее в этом ответе, существует бесконечно много n таких, что1/(n2+j)<ProbO[AO(n,zO(n))], так что есть такой многочлен, что

последовательность, чья n-я запись является наименьшим лексикографическим
[контур С размера, ограниченного сверху этим полиномом], который максимизируетPrx{0,1}n[R(x,C(x))]

является P / poly алгоритмом, вероятность которого (по выбору x) найти решение не пренебрежимо мала.


Поэтому смысл в теле моего вопроса всегда держится.

Чтобы получить то же значение для других игр полиномиальной длины, просто
измените это доказательствоA чтобы сделать это иметь входные схемы оракула играть в игру.


источник