Creating and sharing knowledge for telecommunications

Session - Computational Complexity of the GPAC

on 29-11-2013


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.

More Information..