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

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






Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика»
24 декабря 2018 г. 16:55–17:30, г. Москва, МИАН, ул. Губкина, д. 8, конференц-зал, 9 этаж
 


Цейтинские формулы и однопроходные ветвящиеся программы

Д. М. Ицыксон

Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук
Видеозаписи:
MP4 733.9 Mb
MP4 333.3 Mb

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

Д. М. Ицыксон
Фотогалерея



Аннотация: Пусть $G$ — связный неориентированный граф с нечетным числом вершин, каждое ребро графа помечено нулем или единицей, мы рассмотрим две задачи: в первой задаче требуется проверить, верно ли что для всех вершин графа сумма пометок инцидентных им ребер четна. Во второй задаче требуется найти вершину, в которой сумма пометок инцидентных ей ребер четна. В докладе пойдет речь о том, как связаны сложности этих задач, если их решать однопроходными ветвящимися программами, а также о связи этих задач со сложностью вывода цейтинских формул в некоторых системах доказательств.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024