On generating all solutions of generalized satisfiability problems

DOI10.1051/ITA/1997310604991MaRDI QIDQ4389761zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Jean-Jacques Hébrard

Publication date 24 May 1998

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92575

zbMATH Keywords

generalized-satisfiability problems

Mathematics Subject Classification ID

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

Recommendations

• Complexity of generalized satisfiability counting problems
• Polynomially solvable satisfiability problems
• Compactly generating all satisfying truth assignments of a Horn formula
• Generating hard satisfiability problems

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Complexity of generalized satisfiability counting problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On generating all maximal independent sets
• On sentences which are true of direct unions of algebras
• On the complexity of H-coloring
• On the Structure of Polynomial Time Reducibility
• The Complexity of Enumeration and Reliability Problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited in

(34)

• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• The complexity of minimal satisfiability problems
• On rainbow-free colourings of uniform hypergraphs
• Enumerating models of DNF faster: breaking the dependency on the formula size
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• Generating clause sequences of a CNF formula
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• Incremental delay enumeration: space and time
• Structural tractability of enumerating CSP solutions
• Paradigms for parameterized enumeration
• Tractability in constraint satisfaction problems: a survey
• Compactly generating all satisfying truth assignments of a Horn formula
• Parameterized enumeration for modification problems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Generating all maximal models of a Boolean expression
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Generating Diverse Solutions in SAT
• On the generator problem
• scientific article; zbMATH DE number 15884 (Why is no real title available?)
• The complexity of surjective homomorphism problems-a survey
• An algebraic hardness criterion for surjective constraint satisfaction.
• Beyond Boolean surjective VCSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• Algorithmically efficient syntactic characterization of possibility domains
• A dichotomy theorem for the inverse satisfiability problem
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Partial Polymorphisms and Constraint Satisfaction Problems
• The weight in enumeration
• Generalized satisfiability problems via operator assignments
• On unique graph 3-colorability and parsimonious reductions in the plane
• Modular SAT-based techniques for reasoning tasks in team semantics
• On the enumeration of signatures of XOR-CNF's

This page was built for publication: On generating all solutions of generalized satisfiability problems

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