Computational complexity of the robust stability problem
Roberto Tempo · 2002
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/sup 2/). 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.>