Previous |  Up |  Next


positive definiteness; stability; nonsingularity; NP-hardness
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
[1] Garey M.E., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. Freeman, San Francisco, 1979. MR 0519066 | Zbl 0411.68039
[2] Nemirovskii A.: Several NP-hard problems arising in robust stability analysis. Math. of Control, Signals, and Systems 6 (1993), 99-105. MR 1358063 | Zbl 0792.93100
[3] Poljak S. and Rohn J.: Checking robust nonsingularity is NP-hard. Math. of Control, Signals, and Systems 6 (1993), 1-9. MR 1358057
[4] Rohn J.: Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl. 15 (1994), 175-184. MR 1257627 | Zbl 0796.65065
Partner of
EuDML logo