The P-matrix problem is co-NP-complete
From MaRDI portal
Publication:1330899
DOI10.1007/BF01582570zbMath0822.90132OpenAlexW2067544030MaRDI QIDQ1330899
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
Abstract computational complexity for mathematical programming problems (90C60) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Related Items
Properties of the Solution Set of Absolute Value Equations and the Related Matrix Classes ⋮ Extended \(P\)-pairs ⋮ Principal minors. I: A method for computing all the principal minors of a matrix ⋮ Principal minors. II: The principal minor assignment problem ⋮ On Relation Between P-Matrices and Regularity of Interval Matrices ⋮ On positivity of principal minors of bivariate Bézier collocation matrix ⋮ Combinatorial characterizations of \(K\)-matrices ⋮ Algorithmic detection and construction of N-matrices ⋮ Generalized Perron Roots and Solvability of the Absolute Value Equation ⋮ Unique end of potential line ⋮ On ``P property and the column-W property ⋮ Sign-solvable linear complementarity problems ⋮ Principal pivot transforms: Properties and applications ⋮ Tolerances, robustness and parametrization of matrix properties related to optimization problems ⋮ Cyclic games and linear programming ⋮ A note on generating \(P\)-matrices ⋮ Box invariance in biologically-inspired dynamical systems ⋮ Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a \(P\)-matrix ⋮ The sum of squared logarithms inequality in arbitrary dimensions ⋮ Good hidden \(P\)-matrix sandwiches ⋮ The fibre of P-matrices: the recursive construction of all matrices with positive principal minors ⋮ The almost semimonotone matrices ⋮ SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection ⋮ An Asymptotic Approach for Testing P0-Matrices ⋮ A marriage matching function with flexible spillover and substitution patterns ⋮ Integrity of systems under decentralized integral control ⋮ On \(P\)-matrices ⋮ Perron-Frobenius theory for complex matrices
Cites Work
