Related Experiment Video
Updated: Feb 28, 2026
10:58
Multimedia Battery for Assessment of Cognitive and Basic Skills in Mathematics BM-PROMA
Published on: August 28, 2021
5.0K
The complexity of divisibility
Johannes Bausch1, Toby Cubitt1,2
1DAMTP, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK.
Linear Algebra and Its Applications
|June 20, 2017
Summary
Finite divisibility of stochastic matrices is NP-complete, while probability distribution divisibility is in P but decomposability is NP-hard. These findings resolve long-standing questions in linear algebra and probability theory.
Area of Science:
- Linear Algebra
- Probability Theory
- Computational Complexity
Background:
- Addresses two long-standing open questions regarding stochastic matrices and probability distributions.
- Focuses on computational complexity aspects of divisibility and decomposability.
Purpose of the Study:
- To determine the computational complexity of finite stochastic matrix divisibility.
- To analyze the complexity of divisibility and decomposability for probability distributions.
- To extend findings to nonnegative matrices and quantum analogues of stochastic matrices.
Main Methods:
- Utilizes computational complexity theory to analyze the problems.
- Develops a polynomial-time algorithm for finite distribution divisibility.
- Proves NP-completeness for stochastic matrix divisibility and NP-hardness for distribution decomposability.
Main Results:
- Finite stochastic matrix divisibility is proven to be NP-complete.
- This result extends to nonnegative matrices and completely-positive trace-preserving maps.
- A complexity hierarchy for probability distributions is established: finite divisibility is in P, while decomposability is NP-hard.
- Results hold for weak-membership formulations, indicating robustness to perturbations.
Conclusions:
- Resolves fundamental questions in linear algebra and probability theory from a computational perspective.
- Establishes clear complexity boundaries for matrix and distribution divisibility/decomposability.
- Provides an efficient algorithm for a key distribution problem.
Related Concept Videos
01:26Long Division of Polynomials
475
Polynomial division is an essential algebraic process to simplify expressions and solve equations. Just as numerical division separates a number into quotient and remainder, polynomial long division partitions a polynomial into simpler components; in this context, the dividend is the polynomial being divided, the divisor is the expression dividing it, and the result is expressed in terms of a quotient and a remainder.The division begins by arranging the dividend and divisor in standard...
475
01:29Complex Zeros
331
Complex zeros are the solutions to polynomial equations that include imaginary numbers, specifically, numbers of the form a + bi, where a and b are real numbers and i is the imaginary unit defined by i2=-1. These zeros satisfy the equation P(x) = 0, where P(x) is a polynomial with real or complex coefficients. Since the complex number system includes all real numbers, it provides a complete framework for analyzing all possible roots of a polynomial.Every polynomial of degree n≥1 can be...
331
01:30Fundamental Theorem of Algebra
348
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the...
348
01:28Synthetic Disvision of Polynomials
230
Synthetic division is an efficient algorithmic approach for dividing a polynomial by a linear binomial of the form x - c, where c is a real number. This method is helpful due to its streamlined process, which avoids the more cumbersome steps involved in the traditional long division of polynomials. It simplifies computation and serves as a practical tool for evaluating polynomials and identifying their factors.To perform synthetic division, one begins by listing the coefficients of the...
230
01:28Partial Fractions
268
A partial fraction is a component of a rational expression represented as the sum of simpler fractions. When a rational function is expressed as a ratio of two polynomials, it can often be decomposed into a sum of fractions whose denominators are simpler polynomials, typically linear or irreducible quadratic factors. This process is called partial fraction decomposition, and it is used to simplify complex expressions for integration, solving equations, or analysis.Partial fraction decomposition...
268
01:29Complex Numbers
367
The real number system cannot represent the square root of a negative number, which restricts solutions for certain equations, such as quadratics with negative discriminants. To address this, the complex number system was developed, introducing the imaginary unit i, where i = √(-1). This extension allows for the representation of all roots, including those involving negative radicands.A complex number is written in the form x + yi, where x and y are real numbers. Here, x represents the...
367