60
в частности, алгоритм, полиномиально много раз обращающийся к полиноми-
ально-временной подпрограмме (и к тому же выполняющий только полиноми-
альные вычисления), сам будет работать в полиномиальном времени.
Наиболее важной характеристикой пренебрежимо малых вероятностей явля-
ется свойство замыкание, рассмотренное нами в предположении 3.6(2): прене-
брежимо малая функция, увеличенная в некоторое полиномиальное количество
раз, остается пренебрежимо малой. В частности, это означает, что если алго-
ритм полиномиально много раз обращается к некоторой подпрограмме, которая
каждый раз в результате такого обращения «терпит неудачу» с пренебрежимо
малой вероятностью, то вероятность того, что какие-либо обращения к этой
подпрограмме
потерпят неудачу, остается пренебрежимо малой.
Достарыңызбен бөлісу: