The Computational Complexity of Equivalence and Isomorphism Problems

Thomas Thierauf

Abstract: A computational model is a framework to do computations according to certain specified rules on some input data. One of the earliest attempts to capture the intuitive notion of an ``algorithm'' was the Turing machine, which is now used as a synonym for it. Today there is a large number of different computational models that are interesting from a theoretical and a practical point of view. These models come for example from automata theory, formal language theory, logic or circuit theory. All models can be considered with additional resource bounds (on the time, for example) or with syntactic restrictions.

In order to understand the computational power of a model, it is very useful to study the following problems with respect to that model:

The theory of computations is the study of the inherent difficulty of computational problems, their computational complexity.

In this thesis, we give an overview over the computational complexity of the satisfiability-, equivalence-, and ``almost'' equivalence problem of various computational models. In particular we consider Boolean formulas, circuits, and various kinds of branching programs.