The sharp-P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a result in computational complexity theory. In 1979 Leslie Valiant proved that computing the permanent of a matrix is sharp-P-hard, even when the matrix is restricted to have entries that are all 0 or 1. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement FormCharacterization Theorem 1 Connections
Sources
1. #P-completeness of 01-permanent (Wikipedia)
Lead sectionQuote, Lead section
The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.