scientific article; zbMATH DE number 1390075

zbMATH Open0940.03051MaRDI QIDQ4934341FDOQ4934341

Authors: Laurent Juban 

Publication date: 13 July 2000

Title of this publication is not available (Why is that?)

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

zbMATH Keywords

unique satisfiabilitysatisfiability problemdichotomy theorempropositional formula

Mathematics Subject Classification ID

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

Cited In (13)

• Minimal distance of propositional models
• As Close as It Gets
• Recognizing frozen variables in constraint satisfaction problems
• Satisfiability with index dependency
• Unique perfect phylogeny is NP-hard
• On the unique satisfiability problem
• Isomorphic implication
• On the structure of solution-graphs for Boolean formulas
• On the Boolean connectivity problem for Horn relations
• k-SAT Is No Harder Than Decision-Unique-k-SAT
• Title not available (Why is that?)
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Satisfiability with index dependency

This page was built for publication:

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