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.
Read more about Permanent Is Sharp-P-complete: Significance, Ben-Dor and Halevi's Proof, Aaronson's Proof
Famous quotes containing the word permanent:
“The energy, the brutality, the scale, the contrast, the tension, the rapid change—and the permanent congestion—are what the New Yorker misses when he leaves the city.”
—In New York City, U.S. public relief program (1935-1943)