The Complexity of Divisibility

Abstract

We address two sets of long-standing open questions in probability theory, from a computational complexity perspective: divisibility of stochastic maps, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic maps 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 maps. 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.

50 pages, 11 figures. Journal-accepted version

References in corpus (1)

• Quantum Subdivision Capacities and Continuous-time Quantum Coding

Cited by in corpus (10)

• Quantum stochastic processes and quantum non-Markovian phenomena
• Operational Characterization of Divisibility of Dynamical Maps
• Number of hidden states needed to physically implement a given conditional distribution
• Pauli semigroups and unistochastic quantum channels
• Fitting quantum noise models to tomography data
• Log-Convex set of Lindblad semigroups acting on $N$-level system
• Quantum and classical dynamical semigroups of superchannels and semicausal channels
• Roots of Completely Positive Maps
• Necessary Criteria for Markovian Divisibility of Linear Maps
• Diffusion and consensus on weakly connected directed graphs