ISSN:
1435-568X
Keywords:
Lyapunov exponent
;
Lyapunov indicator
;
Joint spectral radius
;
Generalized spectral radius
;
Discrete differential inclusion
;
Computational complexity
;
NP-hard
;
Algorithmic solvability
Source:
Springer Online Journal Archives 1860-2000
Topics:
Electrical Engineering, Measurement and Control Technology
,
Mathematics
,
Technology
Notes:
Abstract We analyze the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices are not approximable in polynomial time, and that two related quantities—the lower spectral radius and the largest Lyapunov exponent—are not algorithmically approximable.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01219774
Permalink