The Complexity of Enumeration and Reliability Problems

1979/08/01 by Leslie G. Valiant · 2,130 citations
Computer Science · Mathematics · #Algebraic number #Algorithm #Arithmetic #Artificial intelligence #Bayesian Modeling and Causal Inference #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Complexity class #Computational complexity theory #Computer science #Counting problem #Discrete mathematics #Enumeration #Markov Chains and Monte Carlo Methods #Mathematics #NP-complete #Natural number #Polynomial #Reduction (mathematics) #Reliability (semiconductor) #Time complexity

paper · doi:10.1137/0208032

published in SIAM Journal on Computing 8(3), 410-421 (Society for Industrial and Applied Mathematics)

openalex publication_date 1979/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

The class of # P-complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the NP-complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature.

Citations

• Algorithm 457: finding all cliques of an undirected graph

Cited by

• Counting spanning quasi-trees of ribbon graphs: determinants and #P-completeness
• Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction
• Computing the K-terminal Reliability of Circle Graphs
• Ordered Sets for Data Analysis
• Effectively Counting s-t Simple Paths in Directed Graphs
• Classical and Quantum Algorithms for Topological Invariants of Torus Bundles
• Exact Analysis of k-Connectivity in Secure Sensor Networks with Unreliable Links
• Spanning trees of 3-uniform hypergraphs
• Two remarks concerning balanced matroids
• The complexity of generalized domino tilings
• A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs
• The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)
• Permanents of Circulants: a Transfer Matrix Approach (Expanded Version)
• Spanning connectivity games
• Advances on Matroid Secretary Problems: Free Order Model and Laminar Case
• The n-queens problem
• Lower Bound for (Sum) Coloring Problem
• The random italic k k k -SAT Gibbs uniqueness threshold revisited
• Symmetric Weighted First-Order Model Counting
• Finding Non-Redundant Simpson's Paradox from Multidimensional Data
• On Continuous Local BDD-Based Search for Hybrid SAT Solving
• Approximating Queries on Probabilistic Graphs
• A Scalable Approximate Model Counter
• Lee-Yang theorems and the complexity of computing averages
• Note on Counting Eulerian Circuits
• A Computationally Efficient Method for Learning Exponential Family Distributions
• The Complexity of Planar Counting Problems
• On the Enumeration and Counting of Bicriteria Temporal Paths
• The complexity of solution-free sets of integers
• A survey on checkpointing strategies: Should we always checkpoint à la Young/Daly?
• The Complexity of the Numerical Semigroup Gap Counting Problem
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Attn-JGNN: Attention Enhanced Join-Graph Neural Networks
• Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
• On Budgeted Influence Maximization in Social Networks
• Efficiency of Constant Log Utility Market Makers
• On the complexity of generalized chromatic polynomials
• Modular Counting over 3-Element and Conservative Domains
• Spreaders in the Network SIR Model: An Empirical Study
• On the Complexity of Language Membership for Probabilistic Words
• Computing k-mers in Graphs
• Graphic Realizations of Joint-Degree Matrices
• A Formal Comparison Between Chain-of-Thought and Latent Thought
• Monomial Bases for Broken Circuit Complexes
• Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods
• Determining the Most Promising Selective Backbone Size for Partial Knowledge Compilation
• Holant Problems for Regular Graphs with Complex Edge Functions
• Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage
• The Dichotomy of Conjunctive Queries on Probabilistic Structures
• An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques
• The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
• Exact Computation of Influence Spread by Binary Decision Diagrams
• Counting cocircuits and convex two-colourings is #P-complete
• Efficient Search-Based Weighted Model Integration
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Time-constrained Adaptive Influence Maximization
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one
• Continuous-time quantum walk-based ansätze on neutral atom hardware
• Parameterised Counting Constraint Satisfaction Problems via Holants on Hypergraphs
• Rapid mixing of Glauber dynamics for colorings below Vigoda's 11/6 threshold
• The Thompson-Higman monoids M_k,i: the J-order, the D-relation, and their complexity
• A Combinatorial Problem Arising From Ecology: the Maximum Empower Problem
• Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
• QUBOLite: A lightweigth Python toolkit for QUBO
• Taming Discrete Integration via the Boon of Dimensionality
• The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties
• Expected Outcomes and Manipulations in Online Fair Division
• Numerical Considerations in Weighted Model Counting
• The Complexity of Finding Effectors
• Counting the Number of Solutions to Constraints
• Exploiting Treewidth for Projected Model Counting and its Limits
• From Holant To #CSP And Back: Dichotomy For Holant^c Problems
• Tractable Responsibility Measures for Ontology-Mediated Query Answering
• On zeros and algorithms for disordered systems: mean-field spin glasses
• Generalized Metric Repair on Graphs
• A Proximity Measure using Blink Model
• The Complexity of Approximating Bounded-Degree Boolean \sharp CSP
• Bayesian complementary clustering, MCMC and Anglo-Saxon placenames
• Self-Specifying Machines
• Bounds on the quantum satisfiability threshold
• Boosting Information Spread: An Algorithmic Approach
• Belief Propagation Neural Networks
• On Reliability of Dynamic Addressing Routing Protocols in Mobile Ad Hoc Networks
• Geometric Computations on Indecisive and Uncertain Points
• Maximizing Acceptance Probability for Active Friending in On-Line Social Networks
• Tally NP Sets and Easy Census Functions
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
• An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs
• Maximizing the Spread of Cascades Using Network Design
• Irrelevant Components and Exact Computation of the Diameter Constrained Reliability
• Counting Solutions to Binomial Complete Intersections
• Formalising Hypothesis Virtues in Knowledge Graphs: A General Theoretical Framework and its Validation in Literature-Based Discovery Experiments
• Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
• Uniform Solution Sampling Using a Constraint Solver As an Oracle
• Counting Answer Sets of Disjunctive Answer Set Programs
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Counting Maximum Matchings in Planar Graphs Is Hard
• Ported Tutte Functions of Extensors and Oriented Matroids
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Algorithms for Constructing Overlay Networks For Live Streaming
• Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
• Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE
• Source Detection in Hypergraph Epidemic Dynamics using a Higher-Order Dynamic Message Passing Algorithm
• Tiling simply connected regions with rectangles
• An Extension of the Permutation Group Enumeration Technique (Collapse of the Polynomial Hierarchy: NP = P)
• Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers
• The Query Complexity of a Permutation-Based Variant of Mastermind
• Algorithmic hardness of the partition function for nucleic acid strands
• The parameterized complexity of k-edge induced subgraphs
• Abstracting Probabilistic Models: A Logical Perspective
• Complexity of mixed equilibria in Boolean games
• On Tractable Representations of Binary Neural Networks
• CNFs and DNFs with Exactly k Solutions
• Nesting Probabilistic Inference
• Estimation of Small s-t Reliabilities in Acyclic Networks
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
• Approximate Evaluation of Label-Constrained Reachability Queries
• Computing the Tutte polynomial in vertex-exponential time
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• Hardness of decoding quantum stabilizer codes
• Efficiently Finding a Maximal Clique Summary via Effective Sampling
• Which phylogenetic networks are merely trees with additional arcs?
• Cognitively-constrained learning from neighbors
• Tractable Querying and Learning in Hybrid Domains via Sum-Product Networks
• Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network
• The Complexity of Planar Boolean #CSP with Complex Weights
• Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
• The permanent, graph gadgets and counting solutions for certain types of planar formulas
• To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
• Model Counting meets F0 Estimation
• Mitigating the Curse of Correlation in Security Games by Entropy Maximization
• Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
• Constrained Sampling and Counting: Universal Hashing Meets SAT Solving
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• Finding k-shortest paths with limited overlap
• Sampling Markov Models under Constraints: Complexity Results for Binary Equalities and Grammar Membership
• Matching a Desired Causal State via Shift Interventions
• Stratified Splitting for Efficient Monte Carlo Integration
• Analysis of Breakdown Probability of Wireless Sensor Networks with Unreliable Relay Nodes
• Hardness of Mastermind
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Computing the Tutte Polynomial in Vertex-Exponential Time
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Foundations of Modern Query Languages for Graph Databases
• Adaptive Influence Maximization under General Feedback Models
• The Fundamental Theorem of Perfect Simulation
• Random sampling of colourings of sparse random graphs with a constant number of colours
• The Complexity of Weighted Boolean #CSP
• Computational Properties of Metaquerying Problems
• Complexity of Propositional Abduction for Restricted Sets of Boolean Functions
• Model Counting of Query Expressions: Limitations of Propositional Methods
• Synthesizing Robust Plans under Incomplete Domain Models
• An overview of computational complexity
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes
• Computational Complexity
• The Nature of Computation
• Closure Properties and Characterizations of TotP
• On Approximation Algorithms for # P
• The complexity of computing the permanent
• Polynomial-time inference of all valid implications for Horn and related formulae
• On non-planar, cycle-conformal graphs
• Generating All Vertices of a Polyhedron Is Hard
• Graph factors and factorization: 1985–2003: A survey
• On the computational complexity of the Jones and Tutte polynomials
• Counting models for 2SAT and 3SAT formulae
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Prime Path Coverage in the GNU Compiler Collection
• Counting and Enumerating Independent Sets with Applications to Knapsack Problems
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Hard Enumeration Problems in Geometry and Combinatorics
• Isomorphism testing for graphs of bounded genus
• Beyond NP
• A probabilistic logic programming event calculus
• Counting 4×4 matrix partitions of graphs
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• Projected Model Counting: Beyond Independent Support
• Exploiting independent subformulas: A faster approximation scheme for #k-SAT
• Robust Routing in Interdependent Networks
• Complexity Classifications for Propositional Abduction in Post's Framework
• The complexity of weighted and unweighted #CSP
• Two-dimensional monomer-dimer systems are computationally intractable
• Cycle-Centrality in Economic and Biological Networks
• Tropical Tensor Network for Ground States of Spin Glasses
• Classical Simulation of Quantum Circuits by Half Gauss Sums
• Descriptive complexity and weighted Turing machines
• Systematic Parameter Decision in Approximate Model Counting
• 2-satisfiability [wikipedia]
• P versus NP problem [wikipedia]

Related

• Characterizations and approximability of hard counting classes below #P
• A Complexity Theory for Hard Enumeration Problems
• On the power of counting the total number of computation paths of NPTMs
• Approximate counting and NP search problems
• Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses