16 citations · 16 across the 2 of their papers we have counts for
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★ 16 cited
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…