The complexity of computing the permanent
From MaRDI portal
Publication:600247
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
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A characterization of convertible (0,1)-matrices
- A lower bound on the number of additions in monotone computations
- A method for obtaining digital signatures and public-key cryptosystems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An Algorithm for Distinct Representatives
- Every Prime Has a Succinct Certificate
- Gaussian elimination is not optimal
- On the computational power of pushdown automata
- On the relation between the determinant and the permanent
- Relative complexity of checking and evaluating
- The Complexity of Enumeration and Reliability Problems
- The complexity of theorem-proving procedures
- The polynomial-time hierarchy
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
- On testing monomials in multivariate polynomials
- Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes
- On deterministic approximation of DNF
- A complexity theory of constructible functions and sheaves
- Permanent and determinant
- On the frontiers of polynomial computations in tropical geometry
- Hard Enumeration Problems in Geometry and Combinatorics
- Arithmetization: A new method in structural complexity theory
- On unique graph 3-colorability and parsimonious reductions in the plane
- The structure and complexity of Nash equilibria for a selfish routing game
- The expected characteristic and permanental polynomials of the random Gram matrix
- On the Pólya permanent problem over finite fields
- Feasible arithmetic computations: Valiant's hypothesis
- Singular values of Gaussian matrices and permanent estimators
- A very hard log-space counting class
- Graphs determined by polynomial invariants
- A note on the determinant and permanent problem
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Structure and importance of logspace-MOD class
- Algorithmic uses of the Feferman-Vaught theorem
- Exact algorithms for exact satisfiability and number of perfect matchings
- A \(q\)-analog of approximation inclusion-exclusion
- On the depth complexity of formulas
- Approximating the permanent of graphs with large factors
- On the permanent of certain \((0,1)\) Toeplitz matrices
- On the complexity of convex hulls of subsets of the two-dimensional plane
- NP-completeness of some problems concerning voting games
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- The complexity of power-index comparison
- Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Computing functions with parallel queries to NP
- Solving \#SAT using vertex covers
- Games against nature
- Holant problems for 3-regular graphs with complex edge functions
- Hafnians, perfect matchings and Gaussian matrices
- Classification of a Class of Counting Problems Using Holographic Reductions
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)
