Randomized algorithms for robust control analysis and synthesis have polynomial complexity
Pramod P. Khargonekar, Ashok Tikku · 2002
We consider several robust control analysis and design problems. As has become well known over the last few years, most of these problems are NP hard. We show that if instead of worst-case guaranteed conclusions, one is willing to draw conclusions with a high degree of confidence, then the computational complexity decreases dramatically.