TY - GEN
T1 - Complexity Blowup if Continuous-Time LTI Systems are Implemented on Digital Hardware
AU - Boche, Holger
AU - Pohl, Volker
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85126046884&partnerID=8YFLogxK
U2 - 10.1109/CDC45484.2021.9683404
DO - 10.1109/CDC45484.2021.9683404
M3 - Conference contribution
AN - SCOPUS:85126046884
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 6509
EP - 6514
BT - 60th IEEE Conference on Decision and Control, CDC 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 60th IEEE Conference on Decision and Control, CDC 2021
Y2 - 13 December 2021 through 17 December 2021
ER -