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