THE P-MATRIX PROBLEM IS CO-NP-COMPLETE

被引：52

作者：

COXSON, GE

机构：

[1] Department of Electrical and Computer Engineering, University of Wisconsin-Madison, Madison, 53705, WI

来源：

MATHEMATICAL PROGRAMMING | 1994年 / 64卷 / 02期

关键词：

P-MATRIX; LINEAR COMPLEMENTARITY PROBLEM; INTERVAL MATRIX; NP-COMPLETE;

D O I：

10.1007/BF01582570

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Recently Rohn and Poljak proved that for interval matrices with rank-one radius matrices testing singularitY is NP-complete. This paper will show that given any matrix family belonging to the class of matrix polytopes with hypercube domains and rank-one perturbation matrices, a class which contains the interval matrices, testing singularity reduces to testing whether a certain matrix is not a P-matrix. It follows from this result that the problem of testing whether a given matrix is a P-matrix is co-NP-complete.

引用

页码：173 / 178

页数：6