e-space
Manchester Metropolitan University's Research Repository

P-matrix recognition is co-NP-complete

Foniok, J (2007) P-matrix recognition is co-NP-complete. Computing Research Repository (CoRR).

[img]
Preview

Download (118kB) | Preview

Abstract

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

Impact and Reach

Statistics

Downloads
Activity Overview
9Downloads
57Hits

Additional statistics for this dataset are available via IRStats2.

Actions (login required)

Edit Item Edit Item