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.