277
Поскольку
, простая ал-
гебра
Теперь дальнейшее логически вытекает как простое следствие.
УТВЕРЖДЕНИЕ 7.16 Пусть n будет таким, чтобы
Тогда существует множество Sn ∈
{0, 1}n размера, минимум, 1/2p(n) , такое
что для каждого x ∈
Sn и каждого i справедливо следующее
ДОКАЗАТЕЛЬСТВО Пусть ε(n) = 1/p(n), и примем, что Sn будет множе-
ством, гарантированным предыдущим утверждением.. Нам известно, что для
любого x ∈ Sn имеется
Зафиксируем i ∈ {1, . . . , n}. Если r распределено равномерно, то r ⊕ ei; таким образом
Мы заинтересованы в более низкой ограничивающей вероятности, что A выводит
правильный ответ как для gl(x, r), так и для gl(x, r ⊕ ei); что то же самое, мы хотим
для верхней границы вероятности, при которой A не удается вывести правильный
ответ в любом из этих случаев. Заметим, что r и r ⊕ ei не являются независимыми,
таким образом, мы не можем просто перемножить вероятности неудачных ответов.
Однако, мы можем применить границу объединения (см. предположение A.7) и
сложить вероятности неудачных ответов. То есть, вероятность того, что A является
неправильным или на gl(x, r) или gl(x, r ⊕ ei) равна, не
более чем
и, таким образом, A корректно как на gl(x, r), так и на gl(x, r ⊕ ei) с вероятно-
стью, не менее, чем 1/2 + ε(n). Это доказывает утверждение.
Для остальной части доказательства зададим ε(n) = 1/p(n) и рассмотрим толь-
278
ко те
значения n, для которых
Предыдущее утверждение гласит, что для ε(n)/2 доля входов x, и любой i, ал-
горитм A реагирует правильно как на (f (x), r), так и на (f (x), r ⊕ ei) с вероят-
ностью не менее 1/2 + ε(n) при однородном выборе r, и с этого момента мы
сосредоточимся только на таких значениях x. Построим вероятностный поли-
номиально-временной алгоритм Ar , который инвертирует f (x) с вероятностью
1/2, когда x ∈ Sn.
Этого достаточно, чтобы затем доказать предположение 7.14
для бесконечного множества значений n,
Алгоритм Ar, заданный как вход 1n и y, работает следующим образом:
1. Для i = 1, . . . , n выполним:
• Несколько раз выберем однородное r ∈ {0, 1}n и вычисдим A(y, r) ⊕ A(y, r
⊕
ei) в качестве «оценки» i-го бита прообраза y. После выполнения этой про-
цедуры достаточно много раз (см. ниже), будем считать xi «оценкой» того, что
происходит большую часть времени.
2. Выведем x = x1 • • • xn.
Наметим анализ вероятности того, что Ar правильно инвертирует заданный
вход y. (Мы позволим себе быть немного лаконичнее, поскольку полное дока-
зательство для более трудного случая приведено в следующем разделе). Пусть
y = f (xˆ) и напомним, что мы предполагаем здесь, что n такое, что уравнение
(7.1) справедливо и xˆ ∈ Sn. Зафиксируем некоторое i. Предыдущее требование
предполагает, что оценка A(y, r) ⊕ A(y, r ⊕ ei) равна gl(xˆ, ei) с вероятностью не
менее 1 + ε(n) по выбору r. Получая достаточно много оценок и позволяя xi
быть мажоритарным значением, Ar можно гарантировать, что xi равно gl(xˆ,
ei) с вероятностью не менее 1 − 1 . Конечно, нужно убедиться, что полино-
миально множество оценок достаточное. К счастью, поскольку ε(n) = 1/p(n) для
некоторого полинома p и независимое значение r используется для получения
каждой оценки, граница Чернофф (Chernoff ) (ср. с предположением A.14) по-
казывает, что полиномиально множества оценок достаточно.
Подводя итог, имеем, что для каждого i значение xi, вычисленное Ar , некор-
ректно с вероятностью не более 1/2n.
Граница объединения, таким образом,
279
показывает, что Ar является некорректным для некоторого i с вероятностью
не более n •1/2n= /2. То есть, Ar является правильным для всех i—и, таким об-
разом правильно инвертирует y—с вероятностью не менее 1 − 1/2 = 1/2 . Это
завершает доказательство предположения
Следствие предположения 7.14 заключается в том, что если f является одно-
сторонней функцией, то для любого полиномиально-временного алгоритма A
вероятность того, что A правильно прогнозирует gl(x, r) при заданном (f (x), r),
чаще всего,
незначительно больше, чем 3/4.
Достарыңызбен бөлісу: