Аннотация:
Хорошо известно, что в некоторых ситуациях вероятностные алгоритмы позволяют сделать то, что нельзя сделать детерминированно: скажем, сравнив значения случайной хеш-функции на двух длинных файлах, можно почти наверняка установить, равны они или нет, передав логарифмическое число битов. Вопрос о совпадении классов BPP (вероятностных полиномиальных алгоритмов) и P (полиномиальных алгоритмов) является одним из центральных в computer science. Интересно, что и в абстрактной теории вычислимости бывают ситуации, когда использование вероятностных алгоритмов позволяет сделать больше (и другие, когда это ничего не даёт). Некоторые примеры такого рода будут рассмотрены.
|
