The complexity of computing the permanent

DOI10.1016/0304-3975(79)90044-6zbMath0415.68008OpenAlexW2006912660WikidataQ55885263 ScholiaQ55885263MaRDI QIDQ600247

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 complexity determinant permanent of a matrix

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs ⋮ The minimal \(k\)-core problem for modeling \(k\)-assemblies ⋮ The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ On the skew-permanental polynomials of orientation graphs ⋮ Computing the permanent of (some) complex matrices ⋮ Binary determinantal complexity ⋮ A permanent formula with many zero-valued terms ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Multi-boson correlation sampling ⋮ Complexity versus stability for classes of propositional formulas ⋮ Complexity of counting the optimal solutions ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Hafnians, perfect matchings and Gaussian matrices ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ Faster combinatorial algorithms for determinant and Pfaffian ⋮ Bandit online optimization over the permutahedron ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Stochastic enumeration method for counting NP-hard problems ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Random path method with pivoting for computing permanents of matrices ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ Average-case intractability vs. worst-case intractability ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Permanent versus determinant over a finite field ⋮ On the Pólya permanent problem over finite fields ⋮ Pfaffian graphs embedding on the torus ⋮ Enumerating perfect matchings in \(n\)-cubes ⋮ Optical solution for hard on average \#P-complete instances (using exponential space for solving instances of the permanent) ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ A dichotomy in the complexity of counting database repairs ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ On testing monomials in multivariate polynomials ⋮ The expected characteristic and permanental polynomials of the random Gram matrix ⋮ An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs ⋮ Matching signatures and Pfaffian graphs ⋮ Finding all maximally-matchable edges in a bipartite graph ⋮ Approximating the least hypervolume contributor: NP-hard in general, but fast in practice ⋮ A relation-algebraic approach to simple games ⋮ New permanental bounds for Ferrers matrices ⋮ Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient ⋮ Lower bounds for the determinantal complexity of explicit low degree polynomials ⋮ Computing the permanental polynomials of bipartite graphs by Pfaffian orientation ⋮ Complexity and approximability of the cover polynomial ⋮ The consequences of eliminating NP solutions ⋮ On the Pólya conversion problem for permanents and determinants ⋮ On testing Hamiltonicity of graphs ⋮ Counting problems and ranks of matrices ⋮ Cycle-maximal triangle-free graphs ⋮ The factorization of the permanent of a matrix with minimal rank in prime characteristic ⋮ An upper bound on the number of high-dimensional permutations ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Per-spectral characterizations of graphs with extremal per-nullity ⋮ Per-spectral characterizations of bicyclic networks ⋮ A theory of even functionals and their algorithmic applications ⋮ Independent sets versus perfect matchings ⋮ Computing functions with parallel queries to NP ⋮ Approximation algorithm for DNF under distributions with limited independence ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Mathematical aspects of concept analysis ⋮ Relative entropy optimization and its applications ⋮ On the permanents of circulant and degenerate Schur matrices ⋮ Maximal independent sets in a generalisation of caterpillar graph ⋮ Robust planning with incomplete domain models ⋮ Approximately counting paths and cycles in a graph ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Arithmetization: A new method in structural complexity theory ⋮ Non-deterministic exponential time has two-prover interactive protocols ⋮ Finding a shortest non-zero path in group-labeled graphs via permanent computation ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Leveraging belief propagation, backtrack search, and statistics for model counting ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Exponentially many perfect matchings in cubic graphs ⋮ Calculation of the permanent of a sparse positive matrix ⋮ A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes ⋮ An efficient algorithm for computing permanental polynomials of graphs ⋮ A permanent formula for the Jones polynomial ⋮ Shortest \((A+B)\)-path packing via hafnian ⋮ The combinatorics of N. G. de Bruijn ⋮ Counting and sampling SCJ small parsimony solutions ⋮ Regular expression order-sorted unification and matching ⋮ On the permanental polynomials of matrices ⋮ Almost all trees are co-immanantal ⋮ Maximal independent sets in caterpillar graphs ⋮ Bernoulli measure on strings, and Thompson-Higman monoids. ⋮ New permanent approximation inequalities via identities ⋮ Computing expectations and marginal likelihoods for permutations ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ On the succinct representation of graphs ⋮ On the complexity of counting in the polynomial hierarchy ⋮ A note on enumerative counting ⋮ Similarity of personal preferences: Theoretical foundations and empirical analysis ⋮ Odd \(K_{3,3}\) subdivisions in bipartite graphs ⋮ Approximately counting approximately-shortest paths in directed acyclic graphs ⋮ The complexity of estimating min-entropy ⋮ A dichotomy for real weighted Holant problems

Cites Work

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