BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T191336Z
UID:Seminar-dept-388@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20150709T110000
DTEND:20150709T120000
SUMMARY:School Seminar Series
DESCRIPTION:Prof Olivier Bournez: About the hardness of reachability for ordinary differential equations and discrete time dynamical systems or  Why analog mechanical machines of the 30's are not less powerful than modern computers, and not even slower.\n\nIn this talk we will discuss the hardness of solving reachability questions for dynamical systems over a continuous space. They include discrete time dynamical systems of the form y(t+1)=f(y(t)) and continuous time dynamical systems of the form y'=f(y(t)) where ' denotes derivative.\n\n\n\nFor both of them some computability results where known, but not much was know about the complexity of the problems. We will in particular explain why talking about time complexity is not at all a trivial problem for ordinary differential equations over an unbounded domain, by discussing several previous attempts in literature, and why they intrinsically mostly failed.\n\n\n\nWe will show that the continuous time case where f is a vector of polynomials is nice and related to questions about some old and new analog models of computations. \n\n\n\nWe will show in particular that one can numerically solve such ordinary differential equations in polynomial time in the length of the solution curve. Furthermore, we will show that one can embed the simulation of a Turing machine in such a setting. Consequently, systems of the form y(t+1)=f(y(t)) where  f is a vector of polynomials seems to provide a very nice theory of computability for continuous time systems. \n\n\n\nIn particular, we obtain for the first time a characterization of classical polynomial time, that is to say of complexity class P, in terms of ordinary differential equations only.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=388
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR