Subtractive reductions and complete problems for counting complexity classes

DOI10.1016/j.tcs.2005.03.012zbMath1077.68033OpenAlexW4230626603MaRDI QIDQ2566034

Arnaud Durand, Miki Hermann, Phokion G. Kolaitis

Publication date: 22 September 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.03.012

zbMATH Keywords

Complete problemsCounting complexitySubtractive reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The complexity of counting locally maximal satisfying assignments of Boolean CSPs, Counting minimal unsatisfiable subsets, Complexity of counting the optimal solutions, Unnamed Item, The effect of combination functions on the complexity of relational Bayesian networks, Tractable counting of the answers to conjunctive queries, Understanding the complexity of axiom pinpointing in lightweight description logics, The complexity of weighted counting for acyclic conjunctive queries, Parameterised counting in logspace, Solving projected model counting by utilizing treewidth and its limits, Complexity of Counting the Optimal Solutions, The complexity of Bayesian networks specified by propositional and relational languages, Handling and measuring inconsistency in non-monotonic logics, The complexity of problems for quantified constraints, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, A structured view on weighted counting with relations to counting, quantum computation and applications, Descriptive complexity of \#P functions: a new perspective, THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY, On the counting complexity of propositional circumscription, The Weight in Enumeration, A complexity theory for hard enumeration problems, Counting complexity of propositional abduction, On the Complexity of Query Result Diversification, On the Complexity of Computing Generators of Closed Sets, Default logic and bounded treewidth, Decision Procedures for Multisets with Cardinality Constraints, Definability for model counting, Bernoulli measure on strings, and Thompson-Higman monoids., On the complexity of inconsistency measurement, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The complexity of combinatorial problems with succinct input representation
• Some observations on the connection between counting and recursion
• On counting and approximation
• Circumscription - a form of non-monotonic reasoning
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The complexity of model checking for circumscriptive formulae
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Descriptive complexity of \(\#\)P functions
• A complexity theory for feasible closure properties
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Hard Enumeration Problems in Geometry and Combinatorics
• The Complexity of Enumeration and Reliability Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS