Миры, относительно которых «неуязвимые генераторы» не существуют

10

Неуязвимые генераторы определяются следующим образом:

Пусть R - отношение NP, а M - машина, которая принимает L(R) . Неформально программа является неуязвимым генератором, если на входе 1n она создает пары свидетельства экземпляра (x,w)R , где |x|=n , согласно распределению, при котором любой противник за полиномиальное время, которому дано x не может найти свидетельства того, что xS с заметной вероятностью для бесконечно большого числа длин n .

Неуязвимые генераторы, впервые определенные Abadi et al. нашел много приложений в криптографии.

Существование неуязвимых генераторов основано на предположении, что PNP , однако этого, возможно, недостаточно (см. Также смежную тему ).

Теорема 3 Абади и соавт. В статье, приведенной выше, показано, что любое доказательство существования неуязвимых генераторов не релятивизируется:

Теорема 3. Существует оракул B такой, что PBNPB , и неуязвимые генераторы не существуют относительно B.

Я не понимаю часть доказательства этой теоремы. Пусть обозначает непересекающуюся операцию объединения . Пусть QBF - PSPACE-полный язык выполнимых количественных булевых формул, а K - чрезвычайно разреженный набор строк максимальной колмогоровской сложности. В частности, K содержит одну строку каждой длины ni , где последовательность n1,n2, определяется следующим образом: n1=2 , ni является трижды экспоненциальной по ni1 , дляi>1; еслиxKи|x|=n, тоxимеет колмогоровскую сложностьn.

В статье говорится , что по отношению к B=QBFK , то справедливо , что PNP . Вы можете объяснить? (Также, пожалуйста, уточните, является ли B рекурсивным.)

М.С. Дусти
источник

Ответы:

7

Если бы они просто говорили о (не связанной с ресурсами) сложности Колмогорова, то был бы невычислимым (в противном случае вы могли бы использовать машинное вычисление K для краткого описания строк x K , поскольку все, что вам нужно сделать, это описать машина и длина n от x , и мы имеем K ( x ) = n, но K ( n ) log n ), следовательно, B также будет невычислимым.KKxKnxK(x)=nK(n)lognB

UKU[f(n),g(n)]xd|d|f(|x|)x=U(d)U(d)g(|x|)PNP

tow3(1)=2tow3(n+1)=222nCC{1tow3(n):n1}CTIME[nlogn]Ptow3(n)K[logn,nlogn]K[logn,nloglogn]K1tow3(n)CC={1n:(x)[|x|=n and xK]}CNPK

CPKPKNPKCPKMC=L(MK)CPCx=1tow3(n0)

  1. K|x|logloglog|x|U(d)d|x|

  2. M(x)M(x)|x|

yKMK yyyK[logn,nk]nkMy K[logn,nloglogn]

Джошуа Грохов
источник
Очень подробно и хорошо написано. Спасибо, Джошуа!
MS Dousti