2026-07-25T23:33:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22179 2024-12-04T06:53:45Z ddc:004 open_access

Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs MIT Hardness Group Brunner, Josh Demaine, Erik D. Diomidova, Jenny Gomez, Timothy Hecher, Markus Stock, Frederick Zhou, Zixiang Counting Computational Complexity Sharp-P Dichotomy Constraint Graph Satisfiability To prove #P-hardness, a single-call reduction from #2SAT needs a clause gadget to have exactly the same number of solutions for all satisfying assignments - no matter how many and which literals satisfy the clause. In this paper, we relax this condition, making it easier to find #P-hardness reductions. Specifically, we introduce a framework called Generalized #SAT where each clause contributes a term to the total count of solutions based on a given function of the literals. For two-variable clauses (a natural generalization of #2SAT), we prove a dichotomy theorem characterizing when Generalized #SAT is in FP versus #P-complete. Equipped with these tools, we analyze the complexity of counting solutions to Constraint Graph Satisfiability (CGS), a framework previously used to prove NP-hardness (and PSPACE-hardness) of many puzzles and games. We prove CGS ASP-hard, meaning that there is a parsimonious reduction (with algorithmic bijection on solutions) from every NP search problem, which implies #P-completeness. Then we analyze CGS restricted to various subsets of features (vertex and edge types), and prove most of them either easy (in FP) or hard (#P-complete). Most of our results also apply to planar constraint graphs. CGS is thus a second powerful framework for proving problems #P-hard, with reductions requiring very few gadgets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik MIT Hardness Group and Josh Brunner and Erik D. Demaine and Jenny Diomidova and Timothy Gomez and Markus Hecher and Frederick Stock and Zixiang Zhou 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.51 urn:nbn:de:0030-drops-221790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.51 eng https://creativecommons.org/licenses/by/4.0/legalcode