Complexity issues in robust stability of linear delay-differential systems (Q1356632)

This paper discusses the linear differential systems with delays: \(\dot x(t)= A_0 x(t) +\sum^p_{k=1} A_k x(t-h_k)\), where \(A_0, \dots, A_p\) are \(n\times n\) constant matrices. Two stability problems concerning the systems, which are: i) asymptotic stability independent of delay; ii) robust asymptotic stability, are shown to be NP-hard. The main idea used in the proofs of the results is to show that the robust stability problems i) and ii) can be formulated as a combinatorial problem \((T\)-knapsack problem), which is known to be NP-hard. Also, another side result of the paper is that checking robust nonsingularity, robust Hurwitz stability, robust Schur stability of a disk matrix are NP-hard problems.