Усредняющий аргумент

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

Пример

Пример: Если каждому человеку нравится хотя бы 1/3 книг в библиотеке, то в библиотеке есть книга, которая нравится как минимум 1/3 людей.

Доказательство: предположим, что существуют $N$ люди и $B$ книги. Каждому человеку нравится как минимум $B/3$ книг. Позвольте людям оставить след в книге, которая им нравится. Тогда будет как минимум $M=(NB)/3$ отметки. Аргумент усреднения утверждает, что существует книга, по крайней мере, $N/3$ отметки на нем. Предположим от противного, что такой книги не существует. Тогда в каждой книге будет меньше, чем $N/3$ отметки. Однако, поскольку существуют $B$ книг, общее количество оценок будет меньше, чем $(NB)/3$, что противоречит тому факту, что существуют по крайней мере $M$ отметки. $\scriptstyle \blacksquare$

Формализованное определение усредняющего аргумента

Пусть X и Y — множества, пусть p — предикат на X × Y и пусть f — действительное число в интервале [0, 1]. Если для каждого x в X и хотя бы f |Y| элементов y в Y удовлетворяют p ( x , y ), то существует y из Y такой, что существует хотя бы f |X| элементы x в X , которые удовлетворяют p ( x , y ).

Существует еще одно определение, определенное с использованием терминологии теории вероятностей .

Позволять $f$ быть какой-то функцией. Аргументом усреднения является следующее утверждение: если у нас есть схема $C$ такой, что $C(x,y)=f(x)$ с вероятностью по крайней мере $\rho$, где $x$ выбирается случайно и $y$ выбирается независимо от некоторого распределения $Y$ над $\{0,1\}^{m}$ (который может быть даже не поддается эффективной выборке ), тогда существует единственная строка $y_{0}\in \{0,1\}^{m}$ такой, что $\Pr _{x}[C(x,y_{0})=f(x)]\geq \rho$.

Действительно, для каждого $y$ определять $p_{y}$ быть $\Pr _{x}[C(x,y)=f(x)]$ затем

$\Pr _{x,y}[C(x,y)=f(x)]=E_{y}[p_{y}]\,$

и тогда это сводится к утверждению, что для каждой случайной величины $Z$, если $E[Z]\geq \rho$ затем $\Pr[Z\geq \rho ]>0$ (это справедливо, поскольку $E[Z]$ представляет собой средневзвешенное значение $Z$ и ясно, что если среднее некоторых значений хотя бы $\rho$ то одно из значений должно быть не менее $\rho$).

Приложение

Этот аргумент широко используется в теории сложности (например, доказательство ${\mathsf {BPP}}\subsetneq {\mathsf {P/poly}}$) и криптографии (например, доказывая, что неотличимое шифрование приводит к семантической безопасности ). Множество подобных приложений можно найти в . книгах Голдрейха