The Complexity of Enumeration and Reliability Problems
Explore this paper's citation graph
Summary
For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems.
- Type
- article
- Published
- 1979-08-01
- Cited by
- 2,287
- References
- 33
- OpenAlex
- https://openalex.org/W2115826669
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:3759261
Keywords
Enumeration, Counting problem, Class (philosophy), Mathematics, Reduction (mathematics)
References
- On the relation between the determinant and the permanent
- Dimer Statistics and Phase Transitions
- On Counting Problems and the Polynomial-Time Hierarchy
- The complexity of theorem-proving procedures
- Dimer problem in statistical mechanics-an exact result
- Algorithm 457: finding all cliques of an undirected graph
- Enumeration of the Elementary Circuits of a Directed Graph
- Permanents
- Applied Combinatorial Mathematics
Cited by
- Towards Efficient Sampling: Exploiting Random Walk Strategies
- On Ranking 1-Way Finitely Ambiguous NL Languages and #P1-Complete Census Functions
- Query Order and Self-Specifying Machines
- Selected Applications of Minimum Cuts in Networks
- Exact Algorithms for Exact Satisfiability Problems
- Heuristics for BDD handling of sum-of-products formulae
- Optimal Network Design for the Spread of Cascades
- Modularity in answer set programs
- Combinatorial and computational properties of a diameter constrained network reliability model
- Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs
- Approximate inference for determinantal point processes
- Shortest Path Games: Computational Complexity of Solution Concepts
- Efficient Evaluation of
- Explaining User Errors in Knowledge Base Completion
- Solving Diagnostic Problems Using Extended Truth Maintenance Systems
- ISOMORPH-FREE EXHAUSTIVE GENERATION OF COMBINATORIAL DESIGNS
- Sociological orbit based mobility profiling and routing for wireless networks
- On matrices that do not have the consecutive ones property
- Diameter-constrained network reliability : properties and computation. (Propriétés et méthodes de calcul de la fiabilité diamètre-bornée des réseaux)
- The exponential complexity of satisfiability problems