P-matrix recognition is co-NP-complete

Simple item page
dc.creatorFoniok, Jan
dc.date2007-10-18
dc.date.accessioned2026-07-07T08:37:05Z
dc.date.available2026-07-07T08:37:05Z
dc.descriptionThis 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.
dc.description9 pages
dc.identifierhttps://arxiv.org/abs/0710.3519
dc.identifierhttp://arxiv.org/abs/0710.3519
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/140282
dc.subjectComputational Complexity
dc.titleP-matrix recognition is co-NP-complete
dc.typetext

Files

Collections

arXiv