The classes of P-, P-0-, R-0-, semimonotone, strictly semimonotone, column
sufficient, and nondegenerate matrices play important roles in studying sol
ution properties of equations and complementarity problems and convergence/
complexity analysis of methods for solving these problems. It is known that
the problem of deciding whether a square matrix with integer/rational entr
ies is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a
unified analysis, that analogous decision problems for the other matrix cl
asses are also co-NP-complete.