NP-completeness of the linear complementarity problem

From MaRDI portal





We consider the linear complementarity problem (q,M) for which the data is the integer column vector \(q\in R^ n\) and the integer square matrix M of order n. GLCP is the decision problem: Does (q,M) have a solution? We show that GLCP is NP-complete in the strong sense.




Cited in
(82)








This page was built for publication: NP-completeness of the linear complementarity problem

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