R. Tempo and V. Cerone, "Robust stability: the computational complexity point of view", Journal of Complexity, 1992, Vol. 8, pp. 265-276.
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.
For polynomials with interval coefficients, Kharitonov has proposed a criterion for stability: namely, to check that all polynomials from an interval family are stable, it is sufficient to check that 4 special polynomials from this family are stable.
The authors show that for polynomials of order $n$, this checking requires $O(n^2)$ computational steps.