268
«часто»). Скорее наоборот, второе условие Определения 7.1 заключается в том, что
существует вероятностный полиномиально-временной алгоритм A и не пренебре-
жимо малая функция γ, такая что A инвертирует f (x) с вероятностью, минимум, γ (n)
(где вероятность выбирают по равномерному из x ∈ {0, 1}n и случайному A). Это,
в свою очередь, означает, что существует положительный многочлен p(•) такой, что
для бесконечного множество значений n алгоритм A инвертирует f с вероятностью
не менее 1/p(n).
Таким образом, если существует алгоритм A, который инвертирует
f с вероятностью n−10 для всех четных значений n (но никогда не может инверти-
ровать f, если n нечетное), то f не является односторонней функцией—даже в том
случае, когда A успешно срабатывает на половине значений n и срабатывает только
с вероятностью n−10 (для
значений n, где он вообще срабатывает).
Достарыңызбен бөлісу: