RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
Video Library
Archive
Most viewed videos

Search
RSS
New in collection





You may need the following programs to see the files






Workshop on Proof Theory, Modal Logic and Reflection Principles
October 17, 2017 10:00, Moscow, Steklov Mathematical Institute
 


Strong alternatives to weak arithmetics

G. Japaridze
Video records:
MP4 1,124.4 Mb
MP4 308.0 Mb

Number of views:
This page:54
Video files:23

G. Japaridze


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

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

Abstract: 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.

Language: English

SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017