BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Safe Recursive Set Functions - Arnold Beckmann\, Swansea Universit
 y
DTSTART:20120601T130000Z
DTEND:20120601T140000Z
UID:TALK38350@talks.cam.ac.uk
CONTACT:Bjarki Holm
DESCRIPTION:Polynomial time computation on finite strings is a central not
 ion in complexity theory. Polynomial time in more general settings has bee
 n considered by several authors. In this talk we will discuss how polynomi
 al time computation can be defined on sets in general. Our approach is bas
 ed on the Bellantoni-Cook scheme characterizing polynomial time on finite 
 strings in terms of "safe recursion" - we denote our class as safe recursi
 ve set functions (SRSF). We establish an exact characterization of the fun
 ctions that can be computed by SRSF functions on hereditarily finite sets.
   Namely\, using a natural interpretation of finite strings as sets\, we p
 rove that the problems decided by safe recursive set functions are exactly
  those computed by an alternating exponential time Turing machine with pol
 ynomially-many alternations. This complexity class has been considered bef
 ore\, and is known to exactly characterize the complexity of validity in t
 he theory of the real numbers as an ordered additive group by Berman.  We 
 also give characterizations of the safe recursive functions acting on arbi
 trary sets using Goedel's L-hierarchy of constructible sets and refinement
 s of it. As a corollary\, we prove that the safe recursive set functions o
 n binary omega-sequences are identical to those defined to be computable i
 n "polynomial time" by Schindler.
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR