The complexity of computing the permanent

1979/01/01 by Leslie G. Valiant, L.G. Valiant · 22 citations
Computer Science · Mathematics · #Advanced Database Systems and Queries #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.1016/0304-3975(79)90044-6

crossref issued 1979/01/01 · crossref published 1979/01/01 · crossref published-print 1979/01/01 · openalex publication_date 1979/01/01 · crossref created 2002/07/25 · crossref deposited 2020/02/05 · openalex created_date 2025/10/10 · crossref indexed 2026/07/23 · openalex updated_date 2026/07/31

Citations

• The complexity of theorem-proving procedures
• The Complexity of Enumeration and Reliability Problems
• New directions in cryptography
• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Cited by

• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Lower Bounds of Algebraic Branching Programs and Layerization
• Average-case analysis of algorithms for matchings and related problems
• Efficient importance sampling for binary contingency tables
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
• On the succinct representation of graphs
• Graph factors and factorization: 1985–2003: A survey
• On the computational complexity of the Jones and Tutte polynomials
• Counting models for 2SAT and 3SAT formulae
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Structural Controllability of Complex Networks Based on Preferential Matching
• 1-Factorizations of Pseudorandom Graphs
• Fast Computation by Block Permanents of Cumulative Distribution Functions of Order Statistics from Several Populations
• Hard Enumeration Problems in Geometry and Combinatorics
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• Graph isomorphism problem
• Graph isomorphism is low for PP
• On Unapproximable Versions of NP-Complete Problems
• The matching problem for bipartite graphs with polynomially bounded permanents is in NC
• ♯P [wikipedia]