The P-matrix problem is co-NP-complete

DOI10.1007/BF01582570MaRDI QIDQ1330899zbMATH OpenOpenAlexFDO

Authors Gregory E. Coxson

Publication date 10 August 1994

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01582570

zbMATH Keywords

interval matriceslinear complementarityNP-completeP-matrix

Mathematics Subject Classification ID

Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Co-NP-completeness of some matrix classification problems
• Checking robust nonsingularity is NP-hard
• Interval P-Matrices
• Several NP-hard problems arising in robust stability analysis
• On \(P\)-matrices

Cites work

• Checking robust nonsingularity is NP-hard
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• Systems of linear interval equations
• The Componentwise Distance to the Nearest Singular Matrix

Cited in

(39)

• Extended \(P\)-pairs
• A recursive test for P-matrices
• Co-NP-completeness of some matrix classification problems
• The sum of squared logarithms inequality in arbitrary dimensions
• Checking robust nonsingularity is NP-hard
• On \(P\)-matrices
• Perron-Frobenius theory for complex matrices
• Principal pivot transforms: Properties and applications
• Algorithmic detection and construction of N-matrices
• Unique end of potential line
• The almost semimonotone matrices
• SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection
• A marriage matching function with flexible spillover and substitution patterns
• On positivity of principal minors of bivariate Bézier collocation matrix
• On ``P property and the column-W property
• Integrity of systems under decentralized integral control
• scientific article; zbMATH DE number 1225855 (Why is no real title available?)
• On Relation Between P-Matrices and Regularity of Interval Matrices
• Tolerances, robustness and parametrization of matrix properties related to optimization problems
• Interval P-Matrices
• The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
• An asymptotic approach for testing \(P_{0}\)-matrices
• Properties of the Solution Set of Absolute Value Equations and the Related Matrix Classes
• Generalized Perron Roots and Solvability of the Absolute Value Equation
• Combinatorial characterizations of \(K\)-matrices
• Strong NP-completeness of a matrix similarity problem
• Computational complexity of the -Ham-Sandwich problem
• An overview of absolute value equations: from theory to solution methods and challenges
• A note on generating P-matrices
• On matrices whose exponential is a P-matrix
• Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix
• On determinantal point processes with nonsymmetric kernels
• On degeneracy in the P-matroid oriented matroid complementarity problem
• Principal minors. I: A method for computing all the principal minors of a matrix
• Principal minors. II: The principal minor assignment problem
• Sign-solvable linear complementarity problems
• Cyclic games and linear programming
• Box invariance in biologically-inspired dynamical systems
• Good hidden \(P\)-matrix sandwiches

This page was built for publication: The P-matrix problem is co-NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1330899)