Co-NP-completeness of some matrix classification problems

DOI10.1007/s101070000161zbMath1028.90072MaRDI QIDQ1591363

Paul Tseng

Publication date: 20 December 2000

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

zbMATH Keywords

NP-completenesscomplementarity problemscolumn sufficient\(P_0\)-semimonotone\(P\)-semimonotone\(R_0\)-semimonotone1-norm maximizationnondegenerate matricesstrictly semimonotone

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Canonical forms, reductions, classification (15A21)

Related Items (5)

On the complexity of computing the handicap of a sufficient matrix ⋮ The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems ⋮ Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a \(P\)-matrix ⋮ Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction ⋮ The almost semimonotone matrices

This page was built for publication: Co-NP-completeness of some matrix classification problems