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

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





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






В Математическом институте им. В.А. Стеклова Российской академии наук
22 июля 2015 г. 15:00, г. Москва, МИАН, ауд. 530
 


A Notion of Polynomial Time Computability for Set Functions

Samuel Buss

University of California, San Diego, Department of Mathematics
Видеозаписи:
MP4 1,833.4 Mb
MP4 465.2 Mb

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

Samuel Buss


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

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

Аннотация: This talk discusses a new notion of polynomial time computability for general sets, based on $\epsilon$-recursion with a Cobham-style bounding using a new smash function tailored for sets. These are called the Cobham Recursive Set Functions (CRSF), and give a notion of polynomial time computability intrinsic to sets. The smash function accommodates polynomial growth rate of both the size of the transitive closure and the rank of sets. For suitable encodings of binary strings as hereditarily finite sets, the CRSF functions are precisely the usual polynomial time computable functions. We also discuss normal forms and closure properties for CRSF. This is joint work with A. Beckmann, S. Friedman, M. Mueller and N. Thapen.

Язык доклада: английский

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