2 papers
cs.CC2003
The Complexity of Boolean Constraint Isomorphism
Elmar Böhler, Edith Hemaspaandra, Steffen Reith +1
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usua…
cs.CC2002
Equivalence and Isomorphism for Boolean Constraint Satisfaction
E. Boehler, E. Hemaspaandra, Steffen Reith +1
A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fixed set B of Boolean functions. We consider…