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)

• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• The operators min and max on the polynomial hierarchy
• Computing the permanent by importance sampling method.
• Sampling Edge Covers in 3-Regular Graphs
• Some results on certain generalized circulant matrices
• On the hardness of the noncommutative determinant
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Volume of convex polytopes equals mixed volume of simplices
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
• Robust self-assembly of graphs
• Counting over non-planar graphs
• Polynomial time algorithm for an optimal stable assignment with multiple partners
• A note on \(\#\mathcal P\)-completeness of NP-witnessing relations
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Generalizations of Opt P to the polynomial hierarchy
• Kasteleyn cokernels and perfect matchings on planar bipartite graphs
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Counting problems in parameterized complexity
• Some Completeness Results on Decision Trees and Group Testing
• Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
• A lower bound for the determinantal complexity of a hypersurface
• Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
• Clifford algebras and approximating the permanent
• On the number of different permanents of some sparse (0,1)-circulant matrices.
• On the hardness of counting problems of complete mappings.
• Inclusion-exclusion for \(k\)-CNF formulas
• Computation of sparse circulant permanents via determinants
• The geometry of dimer models
• Counting propositional models
• Tensor network contractions for \#SAT
• An upper bound for the permanent of \((0,1)\)-matrices.
• On the Permanental Polynomial and Permanental Sum of Signed Graphs
• On the permanent of a random symmetric matrix
• Enumeration of perfect matchings of lattice graphs by Pfaffians
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Some observations on holographic algorithms
• The complexity of power indexes with graph restricted coalitions
• An analysis of Monte Carlo algorithm for estimating the permanent
• Counting complexity of propositional abduction
• Approximate inference in Bayesian networks: parameterized complexity results
• Definability for model counting
• On the values of permanents of (0, 1) circulant matrices with three ones per row
• The complexity of determinacy problem on group testing
• Categorical complexity
• Shortest two disjoint paths in polynomial time
• On the complexity of ranking
• Phase transitions of PP-complete satisfiability problems
• Information and evidence in logic systems
• Approximating permanents and hafnians
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• Combinatorial problems over power sets
• Complexity and Algorithms for Well-Structured k-SAT Instances
• Dempster's rule of combination is {\#}P-complete
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• On proving parameterized size lower bounds for multilinear algebraic models
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• Graph isomorphism is low for PP
• The complexity of problems for quantified constraints
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Counting vertices of integral polytopes defined by facets
• On the permanental nullity and matching number of graphs
• A duality between Boolean functions
• A loop-free algorithm for generating the linear extensions of a poset
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• 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
• 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
• Counting integral points in polytopes via numerical analysis of contour integration
• 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
• 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
• Bernoulli measure on strings, and Thompson-Higman monoids.
• The computational complexity of evolutionarily stable strategies
• On the complexity of counting in the polynomial hierarchy

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)