The complexity of computing the permanent

DOI10.1016/0304-3975(79)90044-6zbMATH Open0415.68008DBLPjournals/tcs/Valiant79OpenAlexW2006912660WikidataQ55885263 ScholiaQ55885263MaRDI QIDQ600247FDOQ600247

Authors: Leslie G. Valiant 

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90044-6

zbMATH Keywords

computational complexitydeterminantpermanent of a matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)

Cites Work

• Title not available (Why is that?)
• A characterization of convertible (0,1)-matrices
• A method for obtaining digital signatures and public-key cryptosystems
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Enumeration and Reliability Problems
• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On the computational power of pushdown automata
• A lower bound on the number of additions in monotone computations
• The polynomial-time hierarchy
• Relative complexity of checking and evaluating
• On the relation between the determinant and the permanent
• Title not available (Why is that?)
• An Algorithm for Distinct Representatives
• Every Prime Has a Succinct Certificate
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• A loop-free algorithm for generating the linear extensions of a poset
• The Complexity of Computing the Random Priority Allocation Matrix
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Approximate counting for complex-weighted Boolean constraint satisfaction problems
• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• New upper bound for the \#3-SAT problem
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Nilpotent quantum mechanics
• Enumerative counting is hard
• Algorithms and Complexity for Turaev-Viro Invariants
• On the complexity of immanants
• The Second Immanantal Polynomial and the Centroid of a Graph
• Calculation of the permanent of a sparse positive matrix
• A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
• Similarity of personal preferences: Theoretical foundations and empirical analysis
• The permanental process
• \texttt{QOptCraft}: a python package for the design and study of linear optical quantum systems
• Turing machines with few accepting computations and low sets for PP
• A permanent formula for the Jones polynomial
• Shortest \((A+B)\)-path packing via hafnian
• Per-spectral characterizations of some bipartite graphs
• An oracle builder's toolkit
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Relativized counting classes: Relations among thresholds, parity, and mods
• Counting and sampling SCJ small parsimony solutions
• The combinatorics of N. G. de Bruijn
• Regular expression order-sorted unification and matching
• Matching signatures and Pfaffian graphs
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• The Power of Self-Reducibility: Selectivity, Information, and Approximation
• Fast computation of discrete invariants associated to a differential rational mapping
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• Almost all trees are co-immanantal
• A hybrid algorithm for computing permanents of sparse matrices
• Coloring invariants of knots and links are often intractable
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
• Bernoulli measure on strings, and Thompson-Higman monoids.
• The computational complexity of evolutionarily stable strategies
• On the complexity of counting in the polynomial hierarchy
• Immanants and finite point processes
• One complexity theorist's view of quantum computing
• New permanental bounds for Ferrers matrices
• Lower bounds for the determinantal complexity of explicit low degree polynomials
• New permanent approximation inequalities via identities
• On characteristic and permanent polynomials of a matrix
• Fast Computation by Block Permanents of Cumulative Distribution Functions of Order Statistics from Several Populations
• PSPACE is provable by two provers in one round
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Resolving contradictions: A plausible semantics for inconsistent systems
• A relationship between subpermanents and the arithmetic-geometric mean inequality
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• The complexity of the characteristic and the minimal polynomial.
• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• Monomials, multilinearity and identity testing in simple read-restricted circuits
• Comparison of permanental bounds of \((0,1)\)-matrices
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• On the power of parity polynomial time
• The factorization of the permanent of a matrix with minimal rank in prime characteristic
• Per-spectral characterizations of bicyclic networks
• Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration
• Algorithms and complexity for Turaev-Viro invariants
• Cook's versus Valiant's hypothesis
• Permanents of woven matrices
• A theory of even functionals and their algorithmic applications
• Independent sets versus perfect matchings
• Approximation algorithm for DNF under distributions with limited independence
• Odd \(K_{3,3}\) subdivisions in bipartite graphs
• Title not available (Why is that?)
• Approximately counting approximately-shortest paths in directed acyclic graphs
• A dichotomy for real weighted Holant problems
• The complexity of estimating min-entropy
• Finding all maximally-matchable edges in a bipartite graph
• Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
• Characterizing properties of permanental polynomials of lollipop graphs
• Per-spectral characterizations of graphs with extremal per-nullity
• Approximately counting paths and cycles in a graph
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• Masking traveling beams: optical solutions for NP-complete problems, trading space for time
• Tensors in computations
• An upper bound on the number of high-dimensional permutations
• Unification algorithms cannot be combined in polynomial time
• The minimal \(k\)-core problem for modeling \(k\)-assemblies
• On the skew-permanental polynomials of orientation graphs
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Computing the permanent of (some) complex matrices
• Binary determinantal complexity
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The complexity of optimization problems
• Computing small partial coverings
• Random generation of combinatorial structures from a uniform distribution
• A permanent formula with many zero-valued terms
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Nondeterministic \(NC^1\) computation
• New complexity results about Nash equilibria
• Sampling of bosonic qubits
• Multi-boson correlation sampling
• Non-deterministic exponential time has two-prover interactive protocols
• Approximating the number of monomer-dimer coverings of a lattice.
• Complexity versus stability for classes of propositional formulas

This page was built for publication: The complexity of computing the permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q600247)