The complexity of divisibility.
Linear Algebra Appl
MetadataShow full item record
Bausch, J., & Cubitt, T. (2016). The complexity of divisibility.. Linear Algebra Appl, 504 64-107. https://doi.org/10.1016/j.laa.2016.03.041
We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic matrices. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.
60-08, 68Q30, 81-08, Complexity theory, Decomposability, Divisibility, Probability distributions, Stochastic matrices, cptp maps
Johannes Bausch would like to thank the German National Academic Foundation and EPSRC for financial support. Toby Cubitt is supported by the Royal Society. The authors are grateful to the Isaac Newton Institute for Mathematical Sciences, where part of this work was carried out, for their hospitality during the 2013 programme “Mathematical Challenges in Quantum Information Theory”.
Embargo Lift Date
External DOI: https://doi.org/10.1016/j.laa.2016.03.041
This record's URL: https://www.repository.cam.ac.uk/handle/1810/254895
Attribution 4.0 International
Licence URL: http://creativecommons.org/licenses/by/4.0/
Recommended or similar items
The following licence files are associated with this item: