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:
“Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
—Jane Heap (c. 1880–1964)