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

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





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






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


Оптимальные системы доказательств и алгоритмы (обзор)

Э. А. Гирш
Видеозаписи:
Real Video 129.3 Mb
Windows Media 135.3 Mb
Flash Video 203.1 Mb
MP4 203.1 Mb

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

Э. А. Гирш


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

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

Аннотация: Оптимальная система доказательств — система, доказательства в которой не более, чем в полиномиальное количество раз длиннее, чем в любой другой системе. Если к тому же доказательства могут быть переделаны из доказательств в другой системе за полиномиальное время, система называется $p$-оптимальной.
Существование ($p$-)оптимальной системы доказательств для языка пропозициональных тавтологий (и многих других языков) является важным открытым вопросом теории сложности. Я. Крайичек и П. Пудлак (1989) показали связь этого вопроса с существованием оптимальной полуразрешающей процедуры для этого языка. Недавно Х. Монро (2009) доказал отсутствие такой процедуры при некоторых дополнительных предположениях.
В последние годы отсутствие эффективной перечислимости (а значит, и подобного рода универсальных объектов) преодолевалось либо переходом к эвристическим вычислениям (когда имеется вероятностное распределение на входах и допустима ошибка с небольшой вероятностью), либо использованием небольшого количества битов неравномерной подсказки (единой для всех входов одной длины). В частности, С. Кук и Я. Крайичек (2007) показали наличие $p$-оптимальной системы доказательств с неравномерной подсказкой; докладчиком же (совместно с Д. М. Ицыксоном) получена оптимальная полуразрешающая эвристическая процедура для любого полиномиально моделируемого распределения, заданного на дополнении языка.

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