16 citations · 23 across the 4 of their papers we have counts for
4 papers
Complexity classifications for different equivalence and audit problems for Boolean circuits
Elmar Böhler, Nadia Creignou, Matthias Galota +3
We study Boolean circuits as a representation of Boolean functions and consider different equivalence, audit, and enumeration problems. For a number of restricted sets of gate type…
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…
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…
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
Steffen Reith, Heribert Vollmer
We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns ou…