Science, engineering, and life are full of systems that are affected by an outside controller or planner. We consider the computational complexity of determining whether a good control policy or plan exists, and of evaluating a given plan. For instance, in a factory, there may be some program that coordinates and directs the individual machines and robots. The goal of the control program is to maximize productivity. How hard is it to compute the optimal control policy? We have shown that a variety of factors affect complexity: whether the actions have guaranteed or probabilistic effects; the quality of feedback/observations about the current state of the system; what the controller remembers; how the system is represented. I will give several examples from industry and every-day life of controlled stochastic systems to illustrate how the various factors play out. I will also give a quick primer on some familiar and unfamiliar complexity classes (NL, P, NP, PP, and NP^{PP}) in order to discuss our complexity results and their significance. The results discussed are from various recent papers with Eric Allender, Michael Littman, Chris Lusena, and Martin Mundhenk.