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

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






Workshop on Proof Theory, Modal Logic and Reflection Principles
17 октября 2017 г. 10:00–10:35, Москва, Математический институт им. В.А. Стеклова РАН
 


Strong alternatives to weak arithmetics

G. Japaridze
Видеозаписи:
MP4 308.0 Mb
MP4 1,124.4 Mb

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

G. Japaridze



Аннотация: I shall briefly survey arithmetical theories based on the game-semantically conceived Computability Logic. Such theories, dubbed “clarithmetics”, allow us to naturally and systematically capture various computational complexity classes, and do this in a stronger sense than weak arithmetics (e.g. bounded arithmetics) do. Specifically, due to being extensions rather than fragments of PA, clarithmetics achieve not only extensional but also intensional completeness with respect to their target complexity classes. The underlying concept of computability in clarithmetics is also more general than the traditional one, in that it is about interactive problems rather than merely about functions. In this world of interactive computability some unusual phenomena occur. E.g., space complexity is not necessarily upper-bounded by time complexity; not all computable problems have computable time complexities; interactive P has been separated from interactive PSPACE; and more.

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