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

At Steklov Mathematical Institute of Russian Academy of Sciences
July 22, 2015 15:00, Moscow, Steklov Mathematical Institute, Room 530 (8 Gubkina)

A Notion of Polynomial Time Computability for Set Functions

Samuel Buss

University of California, San Diego, Department of Mathematics
 Video records: MP4 1,833.4 Mb MP4 465.2 Mb

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