|
ВИДЕОТЕКА |
Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
|
|||
|
Структурная сложность вероятностных вычислений с ограниченной ошибкой Д. М. Ицыксон |
|||
Аннотация: На данный момент для вероятностных вычислений с ограниченной ошибкой не известно теоремы об иерархии по времени, также не известно полных задач в классе В серии работ (Барак 2002), (Фортноу, Сансанам 2004) и (Мелкебик, Первышев 2007) доказывается иерархия по времени для вероятностных вычислений с ограниченной ошибкой, использующих несколько битов (в лучшем результате используется всего один бит) неравномерной подсказки. Фортноу и Сансанам в 2004 году доказали теорему об иерархии по времени для эвристических алгоритмов, такие алгоритмы могут выдавать неверный ответ на маленькой доле входов. Первышев в 2007 году существенно упростил это доказательство. Докладчиком построена полная задача относительно детерминированных сведений по Тьюрингу и доказана теорема об иерархии по времени в классе |