COMPLEXITY ISSUES IN ROBUST STABILITY OF LINEAR DELAY-DIFFERENTIAL SYSTEMS

In this paper the following stability problems concerning linear delay -differential systems are shown to be NP-hard: (i) asymptotic stabilit y independent of delay, and (ii) robust asymptotic stability, when eac h delay is known to lie in an interval. The main results are based on the NP-hardness of complex bilinear programming over the polydisk (D) over bar(n), which also shows that the purely complex mu computation, analysis/synthesis problems are NP-hard even if there are no repeated blocks. Another side result of the paper is that checking robust nonsi ngularity, robust Hurwitz stability, and robust Schur stability of a d isk matrix are NP-hard problems.