COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Safe Recursive Set Functions

## Safe Recursive Set FunctionsAdd to your list(s) Download to your calendar using vCal - Arnold Beckmann, Swansea University
- Friday 01 June 2012, 14:00-15:00
- Room FW11, Computer Laboratory, William Gates Building.
If you have a question about this talk, please contact Bjarki Holm. Polynomial time computation on finite strings is a central notion in complexity theory. Polynomial time in more general settings has been considered by several authors. In this talk we will discuss how polynomial time computation can be defined on sets in general. Our approach is based on the Bellantoni-Cook scheme characterizing polynomial time on finite strings in terms of “safe recursion” – we denote our class as safe recursive set functions (SRSF). We establish an exact characterization of the functions that can be computed by SRSF functions on hereditarily finite sets. Namely, using a natural interpretation of finite strings as sets, we prove that the problems decided by safe recursive set functions are exactly those computed by an alternating exponential time Turing machine with polynomially-many alternations. This complexity class has been considered before, and is known to exactly characterize the complexity of validity in the theory of the real numbers as an ordered additive group by Berman. We also give characterizations of the safe recursive functions acting on arbitrary sets using Goedel’s L-hierarchy of constructible sets and refinements of it. As a corollary, we prove that the safe recursive set functions on binary omega-sequences are identical to those defined to be computable in “polynomial time” by Schindler. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory talks
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Room FW11, Computer Laboratory, William Gates Building
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsNigeria: Culture, People and Future Immunology and Medicine Seminars The Centre for Music and Science (CMS)## Other talks'Gene regulation in the innate and adaptive immune systems' Research frontiers and new therapeutic strategies in pancreatic cancer Finding meaning in English writing Frontiers in paediatric cancer research Psychological predictors of risky online behaviour: The cases of online piracy and privacy |