Robust stability: The computational complexity point of view

AbstractIn this paper, we explore the new and emerging research area of robust stability and study its interplay with computational complexity. Robust stability deals with a family P consisting of all polynomials p(s, q) of fixed order n whose coefficients vary in a set Q ⊂ Rn+1. The main task of robust stability is to detect if all the roots of p(s, q) are contained in a given region D of the complex plane for all q ϵ Q. In the special case when D is the open left half plane and P is a so-called interval polynomial we combine the Theorem of Kharitonov with the Test of Routh and show that the number of elementary operations (multiplications/divisions and additions/subtractions) required for the solution of this problem is at most O(n2)