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:
“Most Americans are born drunk, and really require a little wine or beer to sober them. They have a sort of permanent intoxication from within, a sort of invisible champagne.... Americans do not need to drink to inspire them to do anything, though they do sometimes, I think, need a little for the deeper and more delicate purpose of teaching them how to do nothing.”
—Gilbert Keith Chesterton (1874–1936)