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

Descripción completa

Detalles Bibliográficos
Autores principales: Bausch, Johannes, Cubitt, Toby
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