LMIs, interior point methods, complexity theory, and robustness analysis

Let δ_Σ be a measure of the relative stability of a stable dynamical system Σ. Let τ_A(Σ) be a measure of the computational efficiency of a particular algorithm A which verifies the stability property of Σ. For two representative cases of Σ, we demonstrate the existence of a particular measure δ_Σ and an algorithm A such that, δ_Στ_A(Σ)=c where c depends possibly on the dimension of the system Σ and parameters which are specific to the algorithm A, but independent of any other system characteristics. In particular, given Σ and A, one can estimate δΣ by measuring τ_A(Σ)