On the computational equivalence of co-NP refutations of a matrix being a P-matrix

Spencer Gordon, Kevin Shu

A P-matrix is a square matrix $X$ such that all principal submatrices of $X$ have positive determinant. Such matrices appear naturally in instances of the linear complementarity pr…