Can I read The Complexity of Checking Partial Total Positivity on EtoBox?

The Complexity of Checking Partial Total Positivity by Carter, Daniel; Johnson, Charles is a scholarly article available to read on EtoBox.

What is The Complexity of Checking Partial Total Positivity about?

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 provide a cubic time algorithm. Checking partial sign regularity with any signature, including partial total nonnegativity, is also co-NP-complete. Finally, we prove that checking partial total positivity in a partial matrix with logarithmically many unspecified entries may be done in polynomial time.

Author

Carter, Daniel; Johnson, Charles

Published

2021

Language

EN