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

    Available under License In Copyright.

    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

    Activity Overview
    6 month trend
    56Downloads
    6 month trend
    286Hits

    Additional statistics for this dataset are available via IRStats2.

    Repository staff only

    Edit record Edit record