275
в i-й позиции и 0 везде, кроме данной точки.. Тогда Ar выводит x = x1 • • • xn.
Очевидно, что Ar работает в течение полиномиального времени.
При выполнении Ar(1n, f (xˆ)),
значение xi,
рассчитанное Ar,
удовлетворяет
Таким образом, xi = xˆi для всех i и тем самым Ar
выводит правильную ин-
версию x = xˆ.
Если f – односторонняя, то для любого вероятностного алгоритма невозмож-
но инвертировать f с пренебрежимо малой вероятностью. Таким образом, мы
приходим к выводу, что не существует полиномиально-временного алгоритма,
который всегда правильно вычисляет gl(x, r) из (f (x), r). Это довольно слабый
результат, что очень далено от нашей цели показать, что gl(x, r) невозможно вы-
числить (с
вероятностью существенно выше, чем 1/2) с учетом (f (x), r).
Достарыңызбен бөлісу: