Amaury Pouly, École Polytechnique
November 29, 2013, Friday, 16h15m.
Abstract: In 1941, Claude Shannon introduced a model for the Differential Analyzer, called the General Purpose Analog Computer (GPAC). Originally it was presented as a model based on circuits, where several units performing basic operations (e.g. sums, integration) are interconnected. However, Shannon itself realized that functions computed by a GPAC are nothing more than solutions of a special class of differential equations of the form y′=p(y) where p is a (vector of) polynomial. Analog computers have since been replaced by digital counterparts. Nevertheless, one can wonder whether the GPAC could in theory have super-Turing computable power. A few years ago, it was shown that Turing-based paradigm and the GPAC have the same computational power. So, switching to analog computers would not enable us to solve the Halting problem, or any uncomputable exotic thing, but we can nonetheless compute everything a Turing machine does (given enough resources), and a return to analog technology would at least not mean a loss of computational power. However, this result did not shed any light on what happens at a computational complexity level: can an analog computer (GPAC) solve a problem faster (modulo polynomial reductions) than a digital computer (Turing machine). I will provide some elements which show that some reasonable restrictions of the GPAC are actually equivalent to P (polynomial time) and NP (nondeterministic polytime), and that there are strong links with Computable Analysis which study the complexity of real functions, at the complexity level.
Room: 3.10, Mathematics
Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2013.