RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика»
18 декабря 2009 г. 17:00, г. Москва
 


Структурная сложность вероятностных вычислений с ограниченной ошибкой

Д. М. Ицыксон
Видеозаписи:
Real Video 127.0 Mb
Windows Media 132.9 Mb
Flash Video 131.2 Mb
MP4 131.2 Mb

Количество просмотров:
Эта страница:262
Видеофайлы:113

Д. М. Ицыксон


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: На данный момент для вероятностных вычислений с ограниченной ошибкой не известно теоремы об иерархии по времени, также не известно полных задач в классе $BPP$ относительно детерминированных сведений. Основное препятствие — это отсутствие вычислимой нумерации вероятностных машин, которые удовлетворяют условию ограниченной ошибки. Хартманис и Хемачандра в 1986 году показали, что существует такой оракул $A$, что в классе $BPP^A$ нет полных языков. Барак в 2002 году показал, что если существует полная задача в классе BPP относительно достаточно сильных детерминированных сведений, то существует и иерархии по времени. Лучший результат, связанный с иерархией по времени суперполиномиальный: Карпинский и Вербик показали, что $BPTime[n^{\log n}]$ строго содержится в $BPTime[2^{n^c}]$ для $c>0$.
В серии работ (Барак 2002), (Фортноу, Сансанам 2004) и (Мелкебик, Первышев 2007) доказывается иерархия по времени для вероятностных вычислений с ограниченной ошибкой, использующих несколько битов (в лучшем результате используется всего один бит) неравномерной подсказки. Фортноу и Сансанам в 2004 году доказали теорему об иерархии по времени для эвристических алгоритмов, такие алгоритмы могут выдавать неверный ответ на маленькой доле входов. Первышев в 2007 году существенно упростил это доказательство.
Докладчиком построена полная задача относительно детерминированных сведений по Тьюрингу и доказана теорема об иерархии по времени в классе $AvgBPP$, который состоит из распределенных задач (языка и полиномиально моделируемого распределения), которые можно решить за полиномиальное в среднем случае (в смысле определения Левина) время вероятностными алгоритмами с ограниченной ошибкой.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017