The Complexity of Checking Partial Total Positivity

Daniel Carter, Charles Johnson

We prove that checking if a partial matrix is partial totally positive is co-NP-complete. This contrasts with checking a conventional matrix for total positivity, for which we prov…