The Complexity of Enumeration and Reliability Problems

1979/08/01 by Leslie G. Valiant · 93 citations
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Bayesian Modeling and Causal Inference #Complexity and Algorithms in Graphs

paper · doi:10.1137/0208032

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\n 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\n 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\n 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\n 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\n 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
• 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\n 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
• 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