Checking positive definiteness or stability of symmetric interval matrices is NP-hard
Rohn, Jiří
Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994), p. 795-797 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard.

Publié le : 1994-01-01
Classification:  15A18,  15A48,  65F30,  65G30,  65Y20,  68Q25 
@article{118721,
     author = {Ji\v r\'\i\ Rohn},
     title = {Checking positive definiteness or stability of symmetric interval matrices is NP-hard},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {35},
     year = {1994},
     pages = {795-797},
     zbl = {0818.65032},
     mrnumber = {1321250},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118721}
}

Rohn, Jiří. Checking positive definiteness or stability of symmetric interval matrices is NP-hard. Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994) pp. 795-797. http://gdmltest.u-ga.fr/item/118721/

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

Nemirovskii A. Several NP-hard problems arising in robust stability analysis, Math. of Control, Signals, and Systems 6 (1993), 99-105. (1993) | MR 1358063 | Zbl 0792.93100

Poljak S. And Rohn J. Checking robust nonsingularity is NP-hard, Math. of Control, Signals, and Systems 6 (1993), 1-9. (1993) | MR 1358057

Rohn J. Positive definiteness and stability of interval matrices, SIAM J. Matrix Anal. Appl. 15 (1994), 175-184. (1994) | MR 1257627 | Zbl 0796.65065