Аннотация:
Известно следующее утверждение: для любых $a<b$ существует язык, распознаваемый некоторым детерминированным алгоритмом за время $O(n^b)$, но не распознаваемый никаким детерминированным алгоритмом за время $O(n^a)$. Данное утверждение называется иерархией детерминированных алгоритмов по времени. Открытым является вопрос о существовании подобной иерархии для вероятностных алгоритмов.
Эвристическими алгоритмами будем называть алгоритмы, которые выдают правильный ответ на 99% входов, но могут ошибаться на 1% входов. Сравнительно недавно Л. Фортноу и Р. Сантанам показали, что иерархия по времени существует для эвристических вероятностных алгоритмов. В докладе рассказывалось простое доказательство этого результата.
|
