Abstract.
The classes of P-, P 0-, R 0-, semimonotone, strictly semimonotone, column sufficient, and nondegenerate matrices play important roles in studying solution 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 entries is a P- (or nondegenerate) matrix is co-NP-complete. We show, through a unified analysis, that analogous decision problems for the other matrix classes are also co-NP-complete.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: April 1999 / Accepted: March 1, 2000¶Published online May 12, 2000
Rights and permissions
About this article
Cite this article
Tseng, P. Co-NP-completeness of some matrix classification problems. Math. Program. 88, 183–192 (2000). https://doi.org/10.1007/s101070000159
Issue Date:
DOI: https://doi.org/10.1007/s101070000159