Complexity Blowup if Continuous-Time LTI Systems are Implemented on Digital Hardware

Abstract

This paper shows that every simple but non-trivial continuous-time, linear time-invariant (LTI) system shows a complexity blowup if its output is simulated on a digital computer. This means that for a given LTI system, a Turing machine can compute a low-complexity input signal in polynomial-time but which yields a corresponding output signal which has high complexity in the sense that the computation time for determining an approximation up to n significant digits grows faster than any polynomial in n. A similar complexity blowup is observed for the calculation of Fourier series approximations and the Fourier transform.