The Complexity of Checking Partial Total Positivity

Publication date 15 March 2021

Matrix completion problems (15A83) Positive matrices and their generalizations; cones of matrices (15B48) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

This page was built for publication: The Complexity of Checking Partial Total Positivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6362941)