This paper provides a comprehensive overview of research related to computational complexity of structured singular value (a.k.a. mu) problems. A survey of computational complexity results in mu problems is followed by a concise introduction to computational complexity theory that is useful to characterize the inherent difficulty of solving an optimization. Results on the study for NP-hardness of epsilon-approximation of mu problems are discussed and conservatism of convex mu upper-bounds including ones obtained from absolute stability theory is studied. NP-hardness of mu computation and conservatism of convex upper-bounds open new research trends. In particular, we give an overview of polynomial-time model reduction methods and probabilistic randomized algorithms that have been active research topics since the mid-1990s. (C) 2013 Elsevier Ltd. All rights reserved.