Permanent Is Sharp-P-complete

Permanent Is Sharp-P-complete

In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.

This result is sometimes known as Valiant's theorem and is considered a seminal result in computational complexity theory. Valiant's 1979 paper also introduced #P as a complexity class.