—A COMPLEXITY THEORETIC PERSPECTIVE ON ROBUSTNESS ANALYSIS

Let 6Z be a measure of the relative stability of a stable dynamical system E defined over the n-dimensional Euclidean space. Let ~A(~) be a mea-sure of the computational efficiency of a particular algorithm A which verifies the stability property of Z by computing a certificate of stability P. We demonstrate the existence of a particular measure 6X and an algorithm A such that, 62 r~(x) = O(n). In addition, we show that & determines the size of the certificate P. These results provide the foun-dation for an algorithmic theory of stability and robustness