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

In this paper, the following robust control problems are shown to be script Nscript P-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∈eH∞∥ℱ(T,Q)∥_μ < 1, for a given linear fractional transformation ℱ(T,Q) with rational coefficients. In other words, purely complex μ computation, analysis, and synthesis problems are script Nscript P-hard. It is also shown that checking 4) stability and 5) computing the H^∞ norm of a multidimensional system, are script Nscript P-hard problems. Therefore, it is rather unlikely to find nonconservative polynomial time algorithms for solving problems 1)-5) in complete generality.