Co-NP-completeness of some matrix classification problems

Authors
Citation
P. Tseng, Co-NP-completeness of some matrix classification problems, MATH PROGR, 88(1), 2000, pp. 183-192
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
88
Issue
1
Year of publication
2000
Pages
183 - 192
Database
ISI
SICI code
0025-5610(200006)88:1<183:COSMCP>2.0.ZU;2-B
Abstract
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.