Co-NP-completeness of some matrix classification problems |
| |
| Authors: | Paul Tseng |
| |
| Institution: | (1) Department of Mathematics, University of Washington, Seattle, Washington 98195, USA, e-mail: tseng@math.washington.edu, US |
| |
| 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.
Received: April 1999 / Accepted: March 1, 2000?Published online May 12, 2000 |
| |
| Keywords: | : P- P0- R0- semimonotone strictly semimonotone column sufficient nondegenerate matrices – complementarity problems – 1-norm maximzation – NP-completeness |
| 本文献已被 SpringerLink 等数据库收录！ |
|
