|Abstract of Paper|
On the Complexity of some Equivalence Problems for Propositional Calculi
by Steffen Reith
In the paper "On the Complexity of some Equivalence Problems for Propositional Calculi" we study the complexity of Boolean equivalence problems (i.e. have two given propositional formulas the same truthtable) and of Boolean isomorphism problems (i.e. does there exists a permutation of the variables of one propositional formula, such that the truthtable of this modified formula coincides with the truthtable of the second formula) of two given generalized propositional formulas and for classes of Boolean circuits built out of gates from an arbitrary finite set.