R. Tempo and V. Cerone, "Robust stability: the
computational complexity point of view", <I> Journal of Complexity</I>,
1992, Vol. 8, pp. 265-276.
<P>

A linear system $\dot x=Ax$ is stable iff its characteristic
polynomial $p(z)=\det(A-zI)$ is stable, i.e., if all its roots have
negative real parts. 
<P>
For polynomials with interval coefficients, Kharitonov has proposed a
criterion for stability: namely, to check that <I> all</I> polynomials
from an interval family are stable, it is sufficient to check that 4
special polynomials from this family are stable. 
<P>
The authors show that for polynomials of order $n$, this checking
requires $O(n^2)$ computational steps.