On the complexity of purely complex μ computation and relatedproblems in multidimensional systems

In this paper, the following robust control problems are shown to be NP-hard: given a purely complex uncertainty structure Δ, determine if: 1) μ_Δ(M)<1, for a given rational matrix M; 2) ∥M(·)∥_μ<1, for a given rational transfer matrix M(s); and 3) inf(Q∈H^∞)∥F(T,Q)∥_μ<1, for a given linear fractional transformation F(T,Q) with rational coefficients. In other words, purely complex μ computation, analysis, and synthesis problems are NP-hard. It is also shown that checking stability and computing the H^∞ norm of a multidimensional system, are NP-hard problems. Therefore, it is rather unlikely to find nonconservative polynomial time algorithms for solving the problems in complete generality