P-matrix recognition is co-NP-complete

2007/10/18 by Jan Foniok, Foniok, Jan
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0710.3519

9 pages

arxiv created 2007/10/18 · openalex publication_date 2007/10/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This is a summary of the proof by G.E. Coxson that P-matrix recognition is co-NP-complete. The result follows by a reduction from the MAX CUT problem using results of S. Poljak and J. Rohn.

Related

• On the computational equivalence of co-NP refutations of a matrix being a P-matrix
• P is a proper subset of NP
• NP-hardness of polytope M-matrix testing and related problems
• Exploring P versus NP
• Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP