P-matrix recognition is co-NP-complete

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

Preview

Available under License In Copyright.
Download (118kB) | Preview

Official URL: https://arxiv.org/corr/home

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].

Item Type:	Article
Peer-reviewed:	Yes
Date Deposited:	19 Apr 2017 08:51
Publisher:	Cornell University Library
Divisions:
Subject terms:	cs.CC, cs.CC
URI:	https://e-space.mmu.ac.uk/id/eprint/618316

Impact and Reach

Statistics

DownloadsShow export options

Activity Overview

6 month trend

58Downloads

6 month trend

295Hits

Additional statistics for this dataset are available via IRStats2.

Repository staff only

Edit record