Cargando…
The complexity of divisibility
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...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
North Holland [etc.]
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5465997/ https://www.ncbi.nlm.nih.gov/pubmed/28626246 http://dx.doi.org/10.1016/j.laa.2016.03.041 |
_version_ | 1783243017234153472 |
---|---|
author | Bausch, Johannes Cubitt, Toby |
author_facet | Bausch, Johannes Cubitt, Toby |
author_sort | Bausch, Johannes |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-5465997 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | North Holland [etc.] |
record_format | MEDLINE/PubMed |
spelling | pubmed-54659972017-06-16 The complexity of divisibility Bausch, Johannes Cubitt, Toby Linear Algebra Appl Article 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. North Holland [etc.] 2016-09-01 /pmc/articles/PMC5465997/ /pubmed/28626246 http://dx.doi.org/10.1016/j.laa.2016.03.041 Text en © 2016 Elsevier Inc. All rights reserved. http://creativecommons.org/licenses/by/4.0/ This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Bausch, Johannes Cubitt, Toby The complexity of divisibility |
title | The complexity of divisibility |
title_full | The complexity of divisibility |
title_fullStr | The complexity of divisibility |
title_full_unstemmed | The complexity of divisibility |
title_short | The complexity of divisibility |
title_sort | complexity of divisibility |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5465997/ https://www.ncbi.nlm.nih.gov/pubmed/28626246 http://dx.doi.org/10.1016/j.laa.2016.03.041 |
work_keys_str_mv | AT bauschjohannes thecomplexityofdivisibility AT cubitttoby thecomplexityofdivisibility AT bauschjohannes complexityofdivisibility AT cubitttoby complexityofdivisibility |