Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинар лаборатории математической логики (Санкт-Петербург)
30 июня 2020 г. 18:30, г. Санкт-Петербург, online
 


What, if anything, can be done in linear time?

Yu. Gurevich

University of Michigan
Видеозаписи:
MP4 109.1 Mb
Дополнительные материалы:
Adobe PDF 262.4 Kb

Количество просмотров:
Эта страница:399
Видеофайлы:39
Материалы:43
Youtube:

Yu. Gurevich



Аннотация: The answer to the title question seems to be “Not much.” Even sorting $n$ items takes $n \times \log ( n )$ swaps. But, in fact, quite a bit can be done in linear time. We start with an illustration of linear-time techniques. Then we sketch the linear-time decision algorithm for propositional primal infon logic. Finally we mention useful extensions of that logic decidable in deterministic or probabilistic linear time.

Дополнительные материалы: gurevich_spb_2020_slides.pdf (262.4 Kb)

Язык доклада: английский
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024