About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Rohn, Jiří
Checking positive definiteness or stability of symmetric interval matrices is NP-hard. (English). Commentationes Mathematicae Universitatis Carolinae, vol. 35 (1994), issue 4, pp. 795-797
MSC: 15A18, 15A48, 65F30, 65G30, 65Y20, 68Q25 | MR 1321250 | Zbl 0818.65032
Keywords:
positive definiteness; stability; nonsingularity; NP-hardness
Summary:
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.
References:
[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