.png){kind=icon}
.png){kind=icon}
Return
Probabilistic solutions to some NP-hard matrix problems
.png){kind=icon}
PRE
AI
DOI：10.1016/S0005-1098(01)00089-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
During recent years, it has been shown that a number of problems in matrix theory are NP-hard, including robust nonsingularity, robust stability, robust positive semidefiniteness. robust bounded norm, state feedback stabilization with structural and norm constraints, etc. In this paper, we use standard bounds on empirical probabilities as well as recent results from statistical learning theory on the VC-dimension of families of sets defined by a finite number of polynomial inequalities, to show that for each of the above problems, as well as for still more general and more difficult problems, there exists a polynomial-time randomized algorithm that can provide a yes or no answer to arbitrarily small levels of accuracy and confidence. (C) 2001 Elsevier Science Ltd. All rights reserved.
Keywords:
NP-hard
matrix stability
VC-dimension
interval matrices
static output feedback
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.