The main role of feedback control is to address the effects of uncertainties, and much of the control literature since the 1980s has involved the analysis and design of uncertain systems. As the complexity of the systems that are being controlled continues to increase, a practical consideration is the computational cost of control analyses and design methods as the system size increases. This paper reviews results on the computational complexity of robust control problems, starting with well-known results and then moving to lesser known results that have broad implications. The paper ends with a discussion of future directions in stochastic robustness analysis.