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 chief element in the art of statesmanship under modern conditions is the ability to elucidate the confused and clamorous interests which converge upon the seat of government. It is an ability to penetrate from the naïve self-interest of each group to its permanent and real interest.... Statesmanship ... consists in giving the people not what they want but what they will learn to want.”
—Walter Lippmann (1889–1974)