Publication:4934341

zbMath0940.03051MaRDI QIDQ4934341

Laurent Juban

Publication date: 13 July 2000

zbMATH Keywords

satisfiability problem; unique satisfiability; dichotomy theorem; propositional formula

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03B05: Classical propositional logic

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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

Related Items

Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, On the Boolean connectivity problem for Horn relations, Recognizing frozen variables in constraint satisfaction problems, Isomorphic implication, Unique Perfect Phylogeny Is NP-Hard