= Leslie G. Valiant
{c}
<Leslie G. Valiant> proved in 1979 that computing the <permanent> of a zero-one <matrix> is complete for the <counting complexity> class $\#\mathbf P$ under the paper's arithmetic reductions.<The Complexity of Computing the Permanent by Leslie G. Valiant>[Theorem1 and reduction construction]{ref}
For a <bipartite graph>'s zero-one <adjacency matrix>, the <permanent> counts <perfect matchings>. Deciding whether one exists admits a <polynomial-time algorithm>, while counting all of them has the paper's much stronger completeness property. This makes the difference between existence and counting concrete. The <permanent> resembles the <determinant> but lacks its alternating signs, so an efficient <determinant> <algorithm> does not automatically compute it. <Valiant's permanent reduction> encodes logical constraints into weighted combinatorial choices.
Back to article page
