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


Conference / Medium

Research Hub

Research Hub A: Kryptographie der Zukunft
Research Hub B: Eingebettete Sicherheit

Research Challenges

RC 2: Quantum-Resistant Cryptography
RC 5: Physical-Layer Security


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.


Coding Theory
Complexity Theory
Information Theory
Implementation Attacks
Post-Quantum Cryptography