Bernd Borchert:

Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages

Download

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.

After the preliminary definitions and observations in Chapter 2 this theorem will be shown in Chapter 3.

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.

The two characterizations of predicate classes and promise classes described above - and their corresponding versions for the recursive case - are the two main results of Part I of this thesis. In Chapter 5 analogous results for some other models of nondeterministic computation will be shown.

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.

This will be interpreted as a non-density result in two ways: (1) on the assumption that the Polynomial Time Hierarchy does not collapse, and (2) for the relativized case. Additionally, the analog of the main result for the log-space case is shown.

Table of contents:

1. Introduction
2. Preliminaries
3. Predicate Classes
4. Promise Classes
5. Analogous Results for Other Nondeterministic Computation Models
6. Predicate Classes Accepted by Regular Languages
7. A Lemma about Regular Languages
8. A Result for Classes Accepted by Regular Languages

Number of pages: 62

---

ISSN 1433-8092 | Imprint