Computer science Randomized, circuit, counting and interactive complexity Theorem

Valiant's theorem on the permanent

Builds on Permanent Nondeterministic Turing machine Polynomial-time reduction

Statement

A function $f \colon \set{0,1}^* \to \N$ is in $\#\mathrm{P}$ if there is a polynomial-time nondeterministic Turing machine $M$ of the following kind. For every $x$ , the number of accepting computation paths of $M$ on $x$ is $f(x)$ . A function $g$ is $\#\mathrm{P}$ -hard if every $f \in \#\mathrm{P}$ is computed in polynomial time by a deterministic machine with an oracle for $g$ .

For an $n \times n$ matrix $A = (a_{ij})$ with entries in $\set{0,1}$ , its permanent is $\operatorname{perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i \sigma(i)}.$ The function $A \mapsto \operatorname{perm}(A)$ is $\#\mathrm{P}$ -complete: it is in $\#\mathrm{P}$ and it is $\#\mathrm{P}$ -hard.

Remarks

The permanent of a $0$ - $1$ matrix $A$ is the number of perfect matchings of the bipartite graph with biadjacency matrix $A$ . So it lies in $\#\mathrm{P}$ : a machine guesses a permutation $\sigma$ and accepts when all $a_{i\sigma(i)}$ equal $1$ . For hardness, Leslie Valiant first reduced the number of satisfying assignments of a formula to the permanent of an integer matrix. His gadgets build a weighted graph whose cycle covers encode the assignments. He then reduced integer entries to $0$ - $1$ entries, using computations modulo a large number.

The determinant has the same formula with the signs $\sgn \sigma$ , and it is computed in polynomial time by Gaussian elimination. So a change of signs separates an easy function from a $\#\mathrm{P}$ -complete one. Deciding whether a bipartite graph has a perfect matching is in P, so the theorem gives a counting problem that is hard although its decision version is easy.

Going deeper

For a student

The theorem started the theory of counting complexity and the class $\#\mathrm{P}$ . Together with Toda's theorem, it shows that an oracle for the permanent decides every problem in the polynomial hierarchy in polynomial time. In algebraic complexity, Valiant's classes VP and VNP have the determinant and the permanent as their model problems. The question whether they differ is an algebraic analogue of P versus NP. The permanent of a matrix with nonnegative entries can still be approximated by a randomised algorithm, a result of Jerrum, Sinclair and Vigoda.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Nondeterministic Turing machine concept
Permanent concept
Polynomial-time reduction concept
Valiant's theorem on the permanent statement

Tag	`E21YAD8156`
URI	`m2://E21YAD8156`
Kind	statement, theorem
Writing	W0 stub
MSC	68Q17, 15A15, 68Q15
Status	This copy of the site has no build data. Run `m2 status E21YAD8156`.
About	Permanent
Uses	Permanent, Nondeterministic Turing machine, Polynomial-time reduction
Changed	3 November 2026