Probabilistic solutions to some NP-hard matrix problems (Q5947649)

Recently, several authors have shown that a number of problems in matrix theory are NP-hard [see, for example \textit{M. R. Garey} and \textit{D. S. Johnson}, Computers and intractability. A guide to the theory of NP-completeness. San Francisco: Freeman (1979; Zbl 0411.68039), and Papadimitrou (1994)], among them robust positive semidefiniteness, robust stability, robust norm boundedness and robust nonsingularity, constant output feedback stabilization with constraints and simultaneous stabilization using constant output feedback. The authors of the present paper show that it is possible to develop polynomial-time randomized algorithms for each of the above-mentioned NP-hard problems. While in the case of Problems 1-4, which are problems of analysis, the randomized algorithms are based on well-established results on Chernoff bounds, in the case of Problem 6 (Problem 5 is a special case of 6), a problem in synthesis, the randomized algorithm uses recent results from statistical learning theory on the Vapnik-Chervonenkis dimension of a family of sets defined by a finite number of polynomial inequalities. The present paper actually develops a broad framework for deriving polynomial-time randomized algorithms for any problem where the decision question to be answered with yes or no can be posed in terms of a finite number of polynomial inequalities.