Computational complexity of the robust stability problem

The author presents some preliminary results on the computational complexity of the robust stability problem. He evaluates upper bounds on the minimal number of elementary operations (multiplications/divisions and additions/subtractions) (COMP) needed to check whether all roots of an nth-order interval polynomial p(s,q ) are contained in a given region D of the complex plane. First, he studies the case when D is the open left half plane and shows that COMP=O(n²). This number of operations is obtained by combining the theorem of Kharitonov and Routh´s algorithm. Subsequently, as a second example, the author takes D equal to the unit disk and considers a class of interval polynomials having perturbations only on about half the coefficients