BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Safe Recursive Set Functions - Arnold Beckmann\, S
wansea University
DTSTART;TZID=Europe/London:20120601T140000
DTEND;TZID=Europe/London:20120601T150000
UID:TALK38350AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/38350
DESCRIPTION:Polynomial time computation on finite strings is a
central notion in complexity theory. Polynomial t
ime in more general settings has been considered b
y several authors. In this talk we will discuss ho
w polynomial time computation can be defined on se
ts in general. Our approach is based on the Bellan
toni-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 t
he functions that can be computed by SRSF function
s on hereditarily finite sets. Namely\, using a n
atural interpretation of finite strings as sets\,
we prove that the problems decided by safe recursi
ve set functions are exactly those computed by an
alternating exponential time Turing machine with p
olynomially-many alternations. This complexity cla
ss has been considered before\, and is known to ex
actly characterize the complexity of validity in t
he theory of the real numbers as an ordered additi
ve group by Berman. We also give characterization
s of the safe recursive functions acting on arbitr
ary sets using Goedel's L-hierarchy of constructib
le sets and refinements of it. As a corollary\, we
prove that the safe recursive set functions on bi
nary omega-sequences are identical to those define
d to be computable in "polynomial time" by Schindl
er.
LOCATION:Room FW11\, Computer Laboratory\, William Gates Bu
ilding
CONTACT:Bjarki Holm
END:VEVENT
END:VCALENDAR