The complexity of counting locally maximal satisfying assignments of Boolean CSPs

DOI10.1016/j.tcs.2016.04.008zbMath1339.68117arXiv1509.03543OpenAlexW2331597986MaRDI QIDQ284575

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 18 May 2016

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

Full work available at URL: https://arxiv.org/abs/1509.03543

zbMATH Keywords

constraint satisfaction problemapproximate computationcomputational complexity of counting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Counting Constraint Satisfaction Problems.

Cites Work

• The complexity of computing the permanent
• Complexity of counting the optimal solutions
• Structure identification of Boolean relations and plain bases for co-clones
• On the counting complexity of propositional circumscription
• An approximation trichotomy for Boolean \#CSP
• How easy is local search?
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• Subtractive reductions and complete problems for counting complexity classes
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Approximately Counting Locally-Optimal Structures
• The Complexity of Enumeration and Reliability Problems
• The complexity of satisfiability problems
• Probability and Computing