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)

• Parameterized counting problems
• Permanental bounds for the signless Laplacian matrix of a unicyclic graph with diameter \(d\)
• Hard Enumeration Problems in Geometry and Combinatorics
• 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
• 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
• 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
• On the algebraic complexity of some families of coloured Tutte polynomials
• 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
• On the coefficients of the permanent and the determinant of a circulant matrix: Applications
• 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
• 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

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)