Complexity of generalized satisfiability counting problems
From MaRDI portal
Publication:1917076
DOI10.1006/inco.1996.0016zbMath0853.68110OpenAlexW2091345559WikidataQ64385460 ScholiaQ64385460MaRDI QIDQ1917076
Publication date: 2 January 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/373168da5db30ff17c26a4c3a012e6c89569c449
Related Items (75)
The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Complexity versus stability for classes of propositional formulas ⋮ The complexity of minimal satisfiability problems ⋮ Complexity of counting the optimal solutions ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Merge-and-Shrink Abstraction ⋮ The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ The Fewest Clues Problem of Picross 3D ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ On the Boolean connectivity problem for Horn relations ⋮ Complexity of tiling a polygon with trominoes or bars ⋮ Tractable counting of the answers to conjunctive queries ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ The complexity of complex weighted Boolean \#CSP ⋮ Holographic algorithms by Fibonacci gates ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ Unnamed Item ⋮ The complexity of weighted and unweighted \(\#\)CSP ⋮ Complexity of Counting the Optimal Solutions ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions ⋮ Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems ⋮ A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs ⋮ The complexity of problems for quantified constraints ⋮ Beyond \#CSP: a dichotomy for counting weighted Eulerian orientations with ARS ⋮ Satisfiability threshold for random XOR-CNF formulas ⋮ Disjunctive closures for knowledge compilation ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ Counting Minimal Dominating Sets ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP ⋮ On the Complexity of Holant Problems ⋮ Counting Constraint Satisfaction Problems. ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Computational complexity of three-dimensional discrete tomography with missing data ⋮ Organization mechanism and counting algorithm on vertex-cover solutions ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ On the complexity of generalized chromatic polynomials ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ On generating all solutions of generalized satisfiability problems ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems ⋮ A computational proof of complexity of some restricted counting problems ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ An approximation trichotomy for Boolean \#CSP ⋮ The complexity of counting homomorphisms seen from the other side ⋮ Algorithms for propositional model counting ⋮ Isomorphic implication ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Counting houses of Pareto optimal matchings in the house allocation problem ⋮ Regular expression order-sorted unification and matching ⋮ The complexity of approximating conservative counting CSPs ⋮ Horn representation of a concept lattice ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The complexity of counting homomorphisms to cactus graphs modulo 2 ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ On the complexity of inconsistency measurement ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ The complexity of partition functions ⋮ Classical simulation of quantum circuits by half Gauss sums
This page was built for publication: Complexity of generalized satisfiability counting problems
