Abstract of Paper

On the Complexity of some Equivalence Problems for Propositional Calculi
by Steffen Reith

Abstract:

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.