The complexity of counting locally maximal satisfying assignments of Boolean CSPs

DOI10.1016/J.TCS.2016.04.008zbMATH Open1339.68117arXiv1509.03543OpenAlexW2331597986MaRDI QIDQ284575FDOQ284575

Mark Jerrum, Leslie Ann Goldberg

Publication date: 18 May 2016

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

Abstract: We investigate the computational complexity of the problem of counting the maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain {0,1}. A satisfying assignment is maximal if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Gamma, #MaximalCSP(Gamma) denotes the problem of counting the maximal satisfying assignments, given an input CSP with constraints in Gamma. We give a complexity dichotomy for the problem of exactly counting the maximal satisfying assignments and a complexity trichotomy for the problem of approximately counting them. Relative to the problem #CSP(Gamma), which is the problem of counting all satisfying assignments, the maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.

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

zbMATH Keywords

approximate computationcomputational complexity of counting problemsconstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (1)

• Counting Constraint Satisfaction Problems.

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The complexity of the counting constraint satisfaction problem 👍 👎
• The complexity of approximating conservative counting CSPs. 👍 👎
• The Complexity of the Counting Constraint Satisfaction Problem 👍 👎
• The complexity of Boolean constraint satisfaction local search problems 👍 👎
• Complexity of generalized satisfiability counting problems 👍 👎
• A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs 👍 👎
• A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs 👍 👎
• The complexity of approximating conservative counting CSPs 👍 👎

This page was built for publication: The complexity of counting locally maximal satisfying assignments of Boolean CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284575)