| Title:
|
Checking positive definiteness or stability of symmetric interval matrices is NP-hard (English) |
| Author:
|
Rohn, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
35 |
| Issue:
|
4 |
| Year:
|
1994 |
| Pages:
|
795-797 |
| . |
| Category:
|
math |
| . |
| Summary:
|
It is proved that checking positive definiteness, stability or nonsingularity of all [symmetric] matrices contained in a symmetric interval matrix is NP-hard. (English) |
| Keyword:
|
positive definiteness |
| Keyword:
|
stability |
| Keyword:
|
nonsingularity |
| Keyword:
|
NP-hardness |
| MSC:
|
15A18 |
| MSC:
|
15A48 |
| MSC:
|
65F30 |
| MSC:
|
65G30 |
| MSC:
|
65Y20 |
| MSC:
|
68Q25 |
| idZBL:
|
Zbl 0818.65032 |
| idMR:
|
MR1321250 |
| . |
| Date available:
|
2009-01-08T18:15:19Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118721 |
| . |
| Reference:
|
[1] Garey M.E., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness.Freeman, San Francisco, 1979. Zbl 0411.68039, MR 0519066 |
| Reference:
|
[2] Nemirovskii A.: Several NP-hard problems arising in robust stability analysis.Math. of Control, Signals, and Systems 6 (1993), 99-105. Zbl 0792.93100, MR 1358063 |
| Reference:
|
[3] Poljak S. and Rohn J.: Checking robust nonsingularity is NP-hard.Math. of Control, Signals, and Systems 6 (1993), 1-9. MR 1358057 |
| Reference:
|
[4] Rohn J.: Positive definiteness and stability of interval matrices.SIAM J. Matrix Anal. Appl. 15 (1994), 175-184. Zbl 0796.65065, MR 1257627 |
| . |
