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?)
- 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)
- Parameterized counting problems
- Permanental bounds for the signless Laplacian matrix of a unicyclic graph with diameter \(d\)
- Algorithms to count paths and cycles
- Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
- Complexity of fundamental problems in probabilistic abstract argumentation: beyond independence
- On the coefficients of the permanent and the determinant of a circulant matrix: applications
- Lee-Yang theorems and the complexity of computing averages
- A note on the permanental roots of bipartite graphs
- Brace generation
- Permanental bounds for the signless Laplacian matrix of bipartite graphs and unicyclic graphs
- On the parameterized complexity of approximate counting
- On sparse hard sets for counting classes
- Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
- Complexity and approximability of the cover polynomial
- Matrix permanent and quantum entanglement of permutation invariant states
- Algorithms for four variants of the exact satisfiability problem
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- An efficient algorithm for computing permanental polynomials of graphs
- Counting classes: Thresholds, parity, mods, and fewness
- Optical solution for hard on average \#P-complete instances (using exponential space for solving instances of the permanent)
- The consequences of eliminating NP solutions
- On some natural complete operators
- Matching signatures and Pfaffian graphs
- Average-case intractability vs. worst-case intractability
- On the permanental polynomials of matrices
- Locating \(P\)/poly optimally in the extended low hierarchy
- On testing Hamiltonicity of graphs
- Counting problems and ranks of matrices
- Cycle-maximal triangle-free graphs
- Identities between dimer partition functions on different surfaces
- On the autoreducibility of functions
- On the power of generalized Mod-classes
- Counting problems over the reals
- Singular spaces of matrices and their application in combinatorics
- On the closure of certain function classes under integer division by polynomially-bounded functions
- The parameterized complexity of probability amplification
- Gap-definable counting classes
- A note on SpanP functions
- Lower bounds against weakly-uniform threshold circuits
- On the Gibson barrier for the Pólya problem
- Farrell polynomials on graphs of bounded tree width
- On the Pólya conversion problem for permanents and determinants
- Counting minimal transversals of \(\beta\)-acyclic hypergraphs
- Division in idealized unit cost RAMs
- Counting perfect matchings in \(n\)-extendable graphs
- Algorithms for Propositional Model Counting
- Complexity of Counting the Optimal Solutions
- Explaining by evidence
- Solution Counting Algorithms for Constraint-Centered Search Heuristics
- The complexity to compute the Euler characteristic of complex varieties
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- No occurrence obstructions in geometric complexity theory
- An asymptotic approximation for the permanent of a doubly stochastic matrix
- Theory of one-tape linear-time Turing machines
- Relative entropy optimization and its applications
- On the permanents of circulant and degenerate Schur matrices
- Maximal independent sets in a generalisation of caterpillar graph
- Leveraging belief propagation, backtrack search, and statistics for model counting
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- Mathematical aspects of concept analysis
- Maximal independent sets in caterpillar graphs
- Robust planning with incomplete domain models
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Counting maximal independent sets in directed path graphs
- An efficient tree decomposition method for permanents and mixed discriminants
- An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence
- Extending matchings in claw-free graphs
- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Finding a shortest non-zero path in group-labeled graphs via permanent computation
- Maximum matchings in scale-free networks with identical degree distribution
- 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
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)
