Leslie G. Valiant proved in 1979 that computing the permanent of a zero-one matrix is complete for the counting complexity class under the paper's arithmetic reductions.[ref]
The Complexity of Computing the Permanent by Leslie G. Valiant. Theorem1 and reduction construction
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.
Articles by others on the same topic
There are currently no matching articles.