**Promoter:** Klaus Ambos-Spies

**Institution:** Universität Heidelberg, Germany

**Date of defence:** December 20th, 1994

** Abstract:**

Several complexity classes - like NP, Parity-P, and PP - are
defined (say *accepted*) by a predicate on computation trees produced
by polynomial time nondeterministic Turing machine computations.
Such classes will be called *predicate classes*. For example NP is
accepted by the predicate on computation trees which is 1 if and only if
the tree contains a leaf with label 1.
As another example, Parity-P is
accepted by the predicate on computation trees which is 1 if and only if
the tree contains an odd number of leaves with label 1.
Call a class a
*principal ideal* if with respect to polynomial time many-one reducibility
it has a complete set and is closed downward.
It is well known that the example classes NP, Parity-P, and PP are principal ideals.
This observation can be generalized:

- The set of predicate classes is equal to the set of principal ideals.

In Chapter 4
complexity classes like UP, BPP, and RP will be considered. These classes
have in common that their original definition can be seen the following way:
there is a
0,1,\bottom-valued function - called *promise function* -
on computation trees
where it is presumed (='promised') for each machine accepting a
language in the class that for each input
the promise function is not \bottom for the corresponding
computation tree. Such classes will be called *promise classes*.
For example UP is defined (say *accepted*) by the
promise function on computation trees
which has the value 0 if the tree does not contain a leaf with label 1, which
has the value 1 if the
tree contains exactly one leaf with label 1, and which has the value \bottom
if the tree contains more than one leaf with label 1.
Call a class an *ideal* if with respect
to polynomial time many-one reducibility it is
closed downward and closed under join.
It is easy to see that the example classes UP, BPP, and RP
are countable ideals. Like before, this observation
can be generalized:

- The set of promise classes is equal to the set of countable ideals.

In Part II of this thesis predicates with a low
complexity will be considered: the
predicates which are determined by a regular language for the
the yields of computation trees (the *yield* is the left-to-right concatenation
of the leaf labels).
For example, NP is accepted by the predicate determined by the
regular language
L which consists of the words containing at least one letter 1.
The main result of Part II
will be the following:

- If the class determined by a regular language L is not equal to P then the class contains at least one of the classes NP, co-NP or MODP_p for p prime.

**Table of contents:**

- Introduction
- Preliminaries
- Predicate Classes
- Promise Classes
- Analogous Results for Other Nondeterministic Computation Models
- Predicate Classes Accepted by Regular Languages
- A Lemma about Regular Languages
- A Result for Classes Accepted by Regular Languages