Dichotomy theorem for generalized unique satisfiability problem

DOI10.1007/3-540-48321-7_27MaRDI QIDQ4934341zbMATH OpenFDO

Authors Laurent Juban

Publication date 13 July 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48321-7_27

zbMATH Keywords

dichotomy theorempropositional formulasatisfiability problemunique satisfiability

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

In 1978 \textit{T. J. Schaefer} [``The complexity of satisfiability problems, Conference Record of the 10th Annual ACM Symposium on Theory of Computing, 1978, 216-226 (1978)] examined the satisfiability problem for propositional formulas of the type ``conjunction of constraints, where the constraints are arbitrary Boolean relations applied to a subset of the input variables. Lately, these satisfiability problems have become known under the name constraint satisfaction problems. Schaefer identified four classes of such formulas (Horn, anti-Horn, affine, and bijunctive) for which the satisfiability problem is polynomial-time solvable, and moreover he proved that in all other cases the satisfiability problem is NP-complete. Since then, a number of researchers have examined different types of satisfiability, counting, and optimization problems for Schaefer-type formulas. Theorems of the above structure are called dichotomy theorems (for particular satisfiability problems). In the present paper, the author examines the question if a given formula has exactly one satisfying assignment. Six classes of formulas are identified for which the problem is polynomial-time solvable, and it is shown that in all other cases the problem is coNP-hard (in fact, complete for the class US; see \textit{A. Blass} and \textit{Y. Gurevich} [Inf. Control 55, 80-88 (1982; Zbl 0543.03027)]). For the entire collection see [Zbl 0921.00033].

Recommendations

• Constraint satisfaction problems: complexity and algorithms
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Mathematical Foundations of Computer Science 2005
• Computational Complexity of Constraint Satisfaction
• scientific article; zbMATH DE number 140384
• Presenting Constraints
• A Dichotomy Theorem for Typed Constraint Satisfaction Problems
• scientific article; zbMATH DE number 4039349
• Colouring, constraint satisfaction, and complexity

Cited in

(15)

• Complexity of generalized satisfiability counting problems
• Isomorphic implication
• Minimal distance of propositional models
• Satisfiability with index dependency
• As Close as It Gets
• On the structure of solution-graphs for Boolean formulas
• Unique perfect phylogeny is NP-hard
• Satisfiability with index dependency
• On the unique satisfiability problem
• k-SAT Is No Harder Than Decision-Unique-k-SAT
• On the strength of uniqueness quantification in primitive positive formulas
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• On the Boolean connectivity problem for Horn relations
• On the maximum-likelihood decoding problem
• Recognizing frozen variables in constraint satisfaction problems

This page was built for publication: Dichotomy theorem for generalized unique satisfiability problem

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