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 satisfiability problem:
given an algorithm of the model,
does there exist an input that is accepted by the algorithm?
-
the equivalence problem:
given two algorithms of the model,
do they compute the same function?
-
the ``almost'' equivalence problem:
given two algorithms of the model,
is there an ``easy'' transformation of the algorithms
such that they compute the same function?
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.