P-matrix recognition is co-NP-complete
classification
💻 cs.CC
keywords
co-np-completep-matrixrecognitioncoxsonfollowspoljakproblemproof
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.