Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages [original]

Inaugural Dissertation

zur

Erlangung der Doktorw¨

urde

der

Naturwissenschaftlich-Mathematischen Gesamtfakult¨

der

Ruprecht-Karls-Universit¨

Heidelberg

vorgelegt von

Diplom-Mathematiker Bernd Borchert

aus L¨

unne im Emsland

1994

F¨

ur meine Eltern

Predicate Classes, Promise Classes, and the

Acceptance Power of Regular Languages

Gutachter: Prof. Dr. Klaus Ambos-Spies, Universit¨

at Heidelberg

Prof. Dr. Klaus W. Wagner, Universit¨

at W¨

urzburg

Tag der m¨

undlichen Pr¨

ufung: 20. Dezember 1994

Preface

Theoretical Computer Science

This Ph.D. thesis was written in the time from January 1991 until July 1994 and

is submitted to the Department of Mathematics of the University of Heidelberg.

It contributes some results to Structural Complexity Theory which is a subfield of

Theoretical Computer Science.

First of all I have to thank my advisor Prof. Klaus Ambos-Spies for his con-

tinuing guidance and support. He also gave several crucial hints for the results of

this thesis.

Also I have to thank Prof. Juris Hartmanis and his former students Richard

Chang, Suresh Chari, Desh Ranjan, and Pankaj Rohatgi. The initial results leading

to this thesis were observed while I was visiting Cornell University in spring 1992.

This is the right place to express gratitude to Prof. Steven Homer and Prof. Ak-

ihiro Kanamori from Boston University who six years ago led me to the interest-

ing field of Structural Complexity Theory. Also I would like to thank Prof. Klaus

Weihrauch, University of Hagen, for supervising my first diploma thesis, and Prof.

Wolfgang Sch¨

onfeld, IBM Heidelberg, for his guidance while I was working in his

group.

For helpful discussions I would like to thank Andreas Eisenbl¨

atter, Ulrich Her-

trampf, Birgit Jenner, Klaus-J¨

orn Lange, Pierre McKenzie, Wolfgang Merkle, An-

dre Nies, Thomas Schwentick, Nikolai Vereshchagin, and Heribert Vollmer.

I am grateful to Prof. Klaus W. Wagner, University of W¨

urzburg, who agreed

to referee this thesis.

The results of Part I of the thesis were presented at the 9th Annual IEEE Con-

ference of Structure in Complexity Theory 1994, see [Bo94b], a journal version

will be submitted. The results of Part II were presented at the 11th Annual Sym-

posium of Theoretical Aspects of Computer Science (STACS) 1994, see [Bo94a],

a journal version will appear in .

Heidelberg, July 1994

Contents

I Predicate Classes and Promise Classes 5

1 Introduction 1

2 Preliminaries 5

3 Predicate Classes 17

4 Promise Classes 22

5 Analogous Results for Other Nondeterministic Computation Models 30

:::::::::::::::::::::::::

:::::::::::::::::::::::::::

:::::::::::::::::::::

:::::::::::::::::

::::::::::::

::::::::::::::

::::::::::::::::::::::::::

:::::::::::::::::::::::::::::::

::::::::::::::::::::::::

:::::::::::::::

::::::::::::

::::::::::::::::

:::::::::::

: :

::::::::::

::::::::::::::::

:::::::::

::::::::::::::::

::::::::::::::::::

1.1 Outline of Part I 1

1.2 Ouline of Part II 2

1.3 Related Work 2

2.1 Order-Theoretic Notions 5

2.2 Recursively Presentable Classes 6

2.3 Polynomial Time Many-One Reducibility 7

2.4 Polynomial Time Many-One Degrees 7

2.5 Principal Ideals 8

2.6 Ideals 11

2.7 Computation Trees 15

3.1 The Definition of Predicate Classes 17

3.2 The Characterization of Predicate Classes 19

4.1 The Definition of Promise Classes 22

4.2 The Characterization of the Promise Classes 24

4.3 Consequences of the Characterization of the Promise Classes 29

5.1 Balanced Polynomial Time Turing Machines 30

5.2 Polynomial Time Bit-Reducibility 31

5.3 Polynomial Time Nondeterministic Transducers 33

5.4 Polynomial Time Function Classes 34

5.5 Relativized Predicate Classes 35

iii

II On the Acceptance Power of Regular Languages 39

::::::::::::

::::::::::::::

::::::::

:::::::::::::::::::::::::

:::::::::::::::::

::::::::::::::::::::::::

:::::::::::::::::::::::::

:::::::::

::::::::::

6 Predicate Classes Accepted by Regular Languages 39

7 A Lemma about Regular Languages 43

8 A Result for Classes Accepted by Regular Languages 48

References 55

Subject Index 63

Symbol Index 64

Index of Classes 65

6.1 Predicate Classes Accepted by Languages 39

6.2 The Definition of Regular Languages 40

6.3 Predicate Classes Accepted by Regular Languages 41

7.1 o-h-Reducibility 43

7.2 Generalized Definite Languages 46

7.3 The Main Lemma 46

8.1 The Main Result 48

8.2 A Non-Density Result on the Assumption that PH does not Collapse 50

8.3 A Non-Density Result for the Relativized Case 51

8.4 An Analogous Result for the Log-Space Case 53

; ;



f ?g

1 Introduction

1.1 Outline of Part I

polynomial time many-one reducibility

polynomial time nondeterministic computation

regular

language

accepted

predicate classes

principal ideal

promise function

Part I of this thesis observes a close connection between two basic concepts of

Structural Complexity Theory, both introduced by Karp in [Ka72]:

1. The concept of which since its defi-

nition was studied intensively, see for example [La75, AS85a].

2. The concept of , in the slightly

more general sence as it is used to define not only the class NP (like in the

original paper) but also classes like P, PP, UP, BPP, and RP.

Part II of this thesis relates the concepts of Part I to the notion of a

More detailed outlines of the two parts and references to related work are given

below.

Several complexity classes – like NP, P, and PP – are defined (say ) by

a predicate on computation trees produced by polynomial time nondeterministic

Turing machine computations. Such classes will be called . 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, 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 if with re-

spect to polynomial time many-one reducibility it has a complete set and is closed

downward. It is well known that the example classes NP, 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 fol-

lowing way: there is a 0 1 -valued function – called – on



Introduction

1.2 Ouline of Part II

1.3 Related Work

promise classes

accepted

ideal

yield

computation trees where it is presumed (=’promised’) for each machine accept-

ing a language in the class that for each input the promise function is not for

the corresponding computation tree. Such classes will be called .

For example UP is defined (say ) 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 if the tree contains more than one leaf with label 1. Call a class an 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 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 is the left-to-right concatenation of the leaf labels). For example, NP is

accepted by the predicate determined by the regular language which consists of

the words containing at least one letter 1.

The main result of Part II will be that if the class determined by a (nontrivial)

regular language is not equal to P then the class contains at least one of the

classes NP, co-NP and MOD P for prime.

This will be interpreted as a non-density result in two ways: (1) on the as-

sumption 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.

Similar work like in Part I was done in Bovet, Crescenzi, and Silvestri in [BCS91,

BCS92], by Vereshchagin in [Ve93], by Hertrampf, Lautemann, Schwentick, Voll-

Introduction

locally definable acceptance types

mod-classes finite acceptance

types

mer, and Wagner in [HL*93], and by Jenner, McKenzie, and Th´

erien in [JMT94].

Like in Part I of this thesis also in these papers the definability of complexity

classes with the help of nondeterministic computation models is investigated.

The classes determined by regular languages, see Part II, were first considered

by Hertrampf, Lautemann, Schwentick, Vollmer, and Wagner in [HL*93]. These

classes are a special case (namely the associative case) of the classes determined

by defined by Hertrampf in [Her92a, Her94b].

On the other hand the and the classes determined by

, considered systematicly in [Her90, Bei91, BG92] and [GW87, Her94a], re-

spectively, are classes which are by definition determined by regular languages.

Introduction

0 0

0 0 0

0 0 0 0 0 0 0 0

Part I

2 Preliminaries

2.1 Order-Theoretic Notions

Predicate Classes and Promise

Classes

()

v 2 v

 2 v 2 v v

2 v v 2

v v v v 2

v v v v v v

v v

R S S S

xRy x; y R R xRx

x S xRy y Rz xRz

xRy y Rx xRy y Rx

x y

R S

i S S xRy i x R i y

S s S

T S s T t s t T

s S s t t s t S

s; s S s s t S

s t s t t s t s t S

s t s t t s t s t t t t

recursively presentable classes

polynomial time many-one reducibility degrees,

principal ideals ideals

computation trees

binary relation

reflexive

transitive symmetric

antisymmetric

preorder

partial order equivalence relation

isomorphic

-complete

-minimum -

maximum

-supremum -infimum

supremum

First some standard order-theoretic notions will be defined in Section 2.1. The

well-known concept of will be defined in Section

2.2. Then the and its notions of

and are presented in the Sections 2.3 – 2.6. Section 2.7

introduces .

The following order-theoretic notions are standard, see for example [Gr78].

A on a set is a subset of . Only the infix notation will

be used, i.e. stands for ( ) . A binary relation is if for

all , it is if from and it follows , it is if

from it follows , and it is if from and it follows

= . A is a reflexive and transitive binary relation on a nonempty set.

A is a preorder which is antisymmetric, and an

is a preorder which is symmetric. A binary relation on a set and a binary

relation on a set are called if there exists an isomorphism, i.e. a

bijective mapping from to such that ( ) ( ).

Let be a preorder on a set . An element is called for

a subset if and holds for all . A (

) is an element such that ( ) for all . For two

elements a ( ) of and is an element

such that and ( and ) and if also for another element

it holds that and ( and ) then ( ). If it is

clear from the context that one is dealing with a preorder , a –supremum will

just be called , this will be done the same way for other order-theoretic

notions.

( )

0 0

0 0 0 0

0 0

0 0 0

0 0

0 0 0

2.2 Recursively Presentable Classes

Predicate Classes and Promise Classes

v v v 2

v v

2 v

2 v v

v 2 v

v v  v

2 6

v 6 v v

6 v

v v v v v

f g

2 f j

h i 2 g h i

f j 2 g

S S S S S

t; a; b S t s s

a b a ; b S a a b b t

a b

S s; s S

s s s s S S

S S

m S s m

t m; s t s

t m s s t

s; s s s

s s t s t t s t s s t

;

z i

A i A x

z ; x A ;

C C A i A

upper semi-lattice

lattice

distributive

-chain

-antichain

-atom

atomic

dense

language

words class

recursively presentable

recursive language

6 Part I

Let be a partial order on a set . Note that for a partial order the supremum

(infimum) of two elements, if it exists, is unique. The partial order is called an

if the supremum exists for every pair of elements, it is called a

if both supremum and infimum exist for every pair of elements. A binary

relation on a set is called an (upper semi-) sublattice of an (upper semi-)

lattice on a set if is a subset of , is the restriction of to , and

is closed under -suprema (and -infima). Note that an (upper semi-) sublattice

is an (upper semi-) lattice. An (upper semi-) lattice is called if for all

elements the following holds: if , where is the supremum of

and , then there are elements such that , , and is the

supremum of and .

Let be a partial order on a set . Two elements are called -

comparable if or . A subset is called a if any two

elements of are comparable, is called an if any two elements are

incomparable. If the minimum exists then an element = is called an

if no element = exists such that . The partial order is called

if for every element = there is an atom such that . A partial

order is called if for any two comparable but different elements there is

an element properly between them, formally: for all for which but not

there is a such that and but neither nor . A partial

order which contains an atom is obviously not dense because there is no element

properly between the minimum and the atom.

In this thesis a will always be a set of words over the alphabet = 0 1 ,

for basic definitions like the one of see for example [HU79]. A is a

set of languages.

Let be the ( + 1)st word of in the length-lexicographic order, see for

example [AS89]. For a language and an IN define to be the language

where is a usual bijective polynomial time computable pairing

function, see for example [BDG88]. Call, like in [BDG88, AS89], a complexity

class if = IN for some recursive , for

the notion of a see for example [HU79].

3 3

Σ Σ

Preliminaries



 2

2 () 2



[ 8 

 8  () 8 

j j f j 2 g

h i

 

 



 () 

8 



f;g f g

2.3 Polynomial Time Many-One Reducibility

2.4 Polynomial Time Many-One Degrees

A B f

x A f x B x

A B

A; B A B A B A

B A; B A B C A; B C A B C

i f

z 

x i f i

z ; x f x

A; B A B A

B B A

A A

A B A B :

A B

A B A

A A A

m;deg

join

polynomial time many-one equivalent

polynomial time many-one degree of a language

trivial

recursive

Let FP denote the class of functions which can be computed by a Tur-

ing machine running in deterministic polynomial time, see for example [HU79,

BDG88] for a more detailed definition. Let denote the polynomial time many-

one reducibility among languages, i.e. if there exists a function FP

such that ( ) for all words . The original definition of this

reducibility is from Karp in [Ka72]. It is easy to see that the binary relation

is a preorder on the set of all languages. Define the of two languages

to be the language 0 1 . The join is a -supremum of and

: and for all languages : .

The following enumeration of FP will be useful. Let in some straightforward

way the deterministic Turing machines which compute functions be

encoded by words. Define for every the function FP to be the function

computed by the following polynomial time deterministic Turing machine: on

input the machine simulates the computation of the deterministic Turing machine

encoded by and cancels the simulation – with output – if the simulated machine

has not terminated after + steps. It is easy to see that FP = IN and

that the function which maps to ( ) is recursive.

For the notions of this section see for example [La75, AS85a]. Two languages

are called , in short , if

and . Note that is an equivalence relation on the set of all languages.

Let the , in short deg ( ), be

the set of languages polynomial time many-one equivalent to , and let

denote the partial order on the -degrees defined by

deg ( ) deg ( ) :

Note that this definition does not depend on the choice of and .

The degree deg ( ) is the unique -supremum of deg ( ) and

deg ( ). This shows that is an upper semi-lattice on the set of all polyno-

mial time many-one degrees.

The two degrees and are called the degrees. Call a degree

deg ( ) if and therefore all languages in deg ( ) are recursive.

Σ Σ

3 3

A I A B B A

A A

A A ;

2.5 Principal Ideals



 f  j  g



 





 f;g  ; f g 

  0f; g

Predicate Classes and Promise Classes

Theorem 2.1 (Ladner 1975, Ambos-Spies 1985a)

m;deg

The following partial orders

are distributive upper semi-lattices, the one in (b) is an upper semi-sublattice of

the one in (a).

(a) The partial order on the set of all nontrivial polynomial time many-one

degrees.

(b) The partial order on the set of the nontrivial recursive polynomial time

many-one degrees. This upper semi-lattice is additionally dense.

principal -ideal principal ideal

lower cone of

downward closure of principal ideal

trivial

8 Part I

Many results are known for the partial order . In this thesis only the

following basic results about density and distributivity due to Ladner in [La75]

and Ambos-Spies in [AS85a], respectively, will be considered.

Call a set of languages a , or simply , if there

exists a language such that = ( ) := . There are

several other names for the class ( ), sometimes it is called

or . For the choice of the name see the next

section. Note that the language is -complete for ( ).

The following classes are examples of principal ideals.

The class NP should be mentioned first as an example of a principal ideal.

Complete languages for NP, like the problem SAT, were – for polynomial

time Turing reducibility – first presented by Cook in [Co71], their -

completeness was shown in [Ka72, Le73]. For a list of -complete prob-

lems for NP see [GJ79]. The fact that for example SAT is not only -

complete for NP but also every language -reducible to SAT is in NP is

easy to see.

The two principal ideals = ( ), = ( ) will be called

principal ideals.

The class P is a principal ideal ( ) where is any language in P .

P contains the two trivial principal ideals and is contained in every nontrivial

principal ideal, see Figure 1.

= 2

Σ Π

∆

Preliminaries

f;g f g









 8





0 @

Figure 1: The two trivial principal ideals and P

Not only P and NP but also all other classes and of the Polyno-

mial Time Hierarchy are principal ideals, the existence of -complete lan-

guages was shown in [St77, Wr77].

Let be any language. Then the class P consisting of all languages com-

putable in polynomial time with oracle (see for example [Co71, BDG88]

and also Section 5.5) is a principal (many-one) ideal according to the results

in [AS86a], see also Corollary 5.8. As a special case, the classes of the

Polynomial Time Hierarchy are principal ideals.

The classes NP(n) and co-NP(n) of the Boolean Hierarchy are principal ide-

als, the existence of -complete languages was shown in [CG*88].

Counting classes like PP, C P, MOD P, P = MOD P, US = 1–NP are

principal ideals, for the original definitions see [Gi77, Wa86b, BG92, PZ83,

BGu82, GW87].

The exponential time classes EXPTIME = DTIME(2poly) and NEXPTIME

= NTIME(2poly) are principal ideals. More generally, the classes -EXPTIME

= DTIME(2...2poly

) and -NEXPTIME = NTIME(2...2poly

), where in

both cases the exponentiation tower has height , can easily be shown to be

principal ideals for every 1. For the exact definitions see for example

[Jo90].

( )

Predicate Classes and Promise Classes

Proposition 2.1

Proof.

Corollary 2.1

Proposition 2.2

Proof.



   ()  () 



   2

 2  

  

   



  ()  ()



 ()

()



 f j 2 g

fh i j 2 g

 f j  g f j 9 2

A; B

A B A B A B :

A B A

A A B A B

A B C A

C B A B

A; B

A B A B A B :

A A A

A B i

B A B j B

B A

C z ; x f x A f

C A B B A B i

m;deg

For all languages it holds:

( ) ( )

For all languages it holds:

( ) ( )

Let be a language. ( ) is recursively presentable

is recursive is recursive.

10 Part I

There is a strong connection between the inclusion order on the principal ideals

and the partial order on the polynomial time many-one degrees.

deg ( ) deg ( )

Note that the second equivalence holds by the definition of . In

order to see the first equivalence assume that ( ) ( ). Because

( ) it holds by the assumption that ( ), this shows . If on

the other side then for each it holds by the transitivity of

that , this shows ( ) ( )

In other words, the inclusion order on the principal ideals is isomorphic to the

-order on the polynomial time many-one degrees. It is clear by the proof that

this isomorphism between the partial order on the degrees and the inclusion order

on the principal ideals exists not only for but for every preorder.

The following corollary follows immediately from Proposition 2.1.

= deg ( ) = deg ( )

By the following proposition the property of being recursively presentable is

determined for a principal ideal by any -complete language.

deg ( )

Note that the second equivalence was already mentioned in the definition

of the recursiveness of a -degree.

In order to see the first equivalence assume that ( ) = IN for

some recursive language . Then = for some IN. But if is recursive

then also = is.

For the other direction let a recursive language be given. Define the language

:= ( ) , the functions were defined in Section 2.3. It is

easy to see that is recursive and that ( ) = = IN :

( )

0 0

2.6 Ideals

Preliminaries

Corollary 2.2

Proposition 2.3

Proof.

8 2 () 2 g f j 2 g



 8



  

 2  

8  8 

 2  



  

   2

x x B f x A C i

A A

A B I C C A B I

A A A

A A B ; B A C

B B C B B A

C A A

I A

I A I A I

A A I A I

The following partial orders are distributive upper semi-lattices.

The one in (b) is an upper semi-sublattice of the one in (a).

(a) The inclusion order on the set of all nontrivial principal ideals.

(b) The inclusion order on the set of all nontrivial recursively presentable principal

ideals. This upper semi-lattice is additionally dense.

-ideal ideal

ideal

(a) The principal ideals are exactly the ideals which have a -

complete language. (b) The recursively presentable principal ideals are exactly

the ideals which have a recursive -complete language.

: ( ) = IN . This finishes the proof of the

fact that the class ( ) is recursively presentable if and only if is recursive.

By Propositions 2.1 and 2.2 the results for the polynomial time many-one de-

grees stated in Theorem 2.1 can be transfered to the principal ideals immediately.

A , or simply , is a nonempty set of languages such that if lan-

guages and are in then each language with is also in .

In other words, an ideal is a nonempty set of languages which is closed under join

und closed downward. The name follows the notation in Lattice Theory, see

for example Gr¨

atzer [Gr78].

The following proposition shows the relation between between ideals and prin-

cipal ideals.

(a) Let a principal ideal ( ) be given. is -complete for ( )

because is in ( ) and by definition all languages in ( ) are -reducible

to . It remains to show that ( ) is an ideal. Let ( ) and

. Then by the supremum property of the join. By the

transitivity of it follows that ( ). Therefore, ( ) is an ideal.

For the other direction let an ideal have a -complete language . It will

be shown that = ( ). It holds ( ) because every language in

is -reducible to . And it holds ( ) because and I is closed

downward.

S S

Σ Π

2 2



IN IN

k k

trivial

ideals

f;g f g



\  \







Predicate Classes and Promise Classes

12 Part I

Part (b) follows from part (a) and Proposition 2.2.

The two trivial principal ideals and will be also be called

. Like in the case of principal ideals it is easy to see that the ideal P contains

the two trivial ideals and every nontrivial ideal contains P.

Some examples of classes are given which are ideals but which are not princi-

pal ideals or not known to be principal ideals.

Classes like UP (defined in [Va76]), BPP, RP (both defined in [Gi77]), FewP

(defined as FNP in [Al86]), and AM (defined in [Ba85]), are easily shown

to be (recursively presentable) ideals. These classes are not known to be

principal ideals, see [Si82, Kow84, AS86b, HH88, Hem88, AS89].

In Proposition 2.5 it will be shown that pairwise intersections of nontrivial

(recursively presentable) ideals are nontrivial (recursively presentable) ide-

als, like (for 1) or ZPP = RP co-RP. Generally, it is not

known if such an intersection is a principal ideal. For a discussion of this

question for the class NP co-NP see [Si82, Kow84, HI85, Hem88, AS89].

(Effective) infinite unions of increasing sequences of (recursively presentable)

ideals, like the class of languages of the Polynomial Time Hierarchy PH=

and the class of languages of the Boolean Hierarchy BH= NP(n),

are (recursively presentable) ideals which are in general not known to be

principal ideals. For the original definitions of PH and BH see [St77, Wr77,

CG*88].

Let the class ELEMENTARY be the union -EXPTIME, for the defini-

tion of the classes -EXPTIME for 1 see the examples of principal ide-

als in Section 2.5. The class ELEMENTARY is a (recursively presentable)

ideal which is provably not a principal ideal because by the Time Hierarchy

Theorem of [HS65] it can be shown for each 1 that -EXPTIME is a

proper subset of ( + 1)-EXPTIME.

The class of all recursive languages is a countable ideal but neither a prin-

cipal ideal nor a recursively presentable ideal.

The class P/poly defined by Karp and Lipton in [KL80, KL82] can easily be

shown to be an ideal. It is not countable, but for example P/poly NP is a

countable ideal.



 



   [



A; B A

A A

I J

Preliminaries

Proposition 2.4

Proof.

Proposition 2.5

(a) Every recursively presentable ideal is a countable ideal. (b)

Every principal ideal is a countable ideal. (c) There is a recursively presentable

ideal which is not a principal ideal. (d) There is a principal ideal which is not

recursively presentable. (e) There is an ideal which is not countable.

The following partial orders are distributive lattices, the one in

(b) is a sublattice of the one in (a), and the one in (c) is a sublattice of the ones in

(a) and (b).

(a) The inclusion order on the set of all nontrivial ideals.

(b) The inclusion order on the set of all nontrivial countable ideals.

In (a), (b) and (c) the infimum of two nontrivial ideals and is given by their

intersection, and the supremum is given by the smallest ideal containing both

and .

The class of all languages is an ideal but not countable.

The following classes are not ideals.

The class E = DTIME(2lin) is recursively presentable, has a -complete

language, and is closed under join but is not an ideal because it is not closed

downward.

A polynomial time many-one degree is an ideal if and only if it is one of the

two trivial degrees because otherwise it is not closed downward.

For two -incomparable recursive languages the class ( )

( ) is recursively presentable and closed downward but is not an ideal

because it is not closed under join.

The relation of the different types of ideals introduced so far is described by

the following Proposition 2.4, see also Figure 2.

(a) Every recursively presentable class is by definition countable. (b) A

principal ideal ( ) is by Proposition 2.3 an ideal, and it is countable because

there are at most countably many -reductions. A witness for (c) is the class

ELEMENTARY, see the examples above, and a witness for (d) is according to

Propositions 2.2 and 2.3 any class ( ) for a non-recursive . A witness for (e)

is the class P/poly, see the examples above.

( ) ( )

Proof.

0 0

i j

Predicate Classes and Promise Classes

 8 2 \

f j 9 2 9 2  8 g

\ \



2 2  8

  

2  2 

  

f j 2 g f j 2 g

I J I J

C A B A; B I J I J A

B C

I J I J

H C A I ; B J C A B

I J

I J I ; J; H K

H I K I J K J

K I J K

A K

A I J

H B I ; C J A B C

A B C

B B ; C C

A B C

I J I J H

I C i J D j C D

14 Part I

recursively presentable principal ideals

recursively presentable ideals principal ideals

countable ideals

ideals

Figure 2: Types of Ideals

(a) Let two nontrivial ideals and be given. It will be shown that

is a nontrivial ideal. Therefore, is the infimum of and . Because both

and contain the class P also the class contains P and is not empty. Let

for two languages , then both and contain

and . Therefore, they contain also by their property of being an ideal. This

shows that is a nontrivial ideal. The supremum of and is the class

= : . It is easy to see that this class is an

ideal, that it contains both and , and that it is contained in every ideal containing

both and . For the distributivity let be as above and let be contained

in . Now it is shown that the supremum of = and = equals

. and and therefore also their supremum are contained in . For the other

direction it obviously suffices to show that for every language in the principal

ideal ( ) is the supremum of two principal ideals in and , respectively.

By definition of there exist sets such that , in

other words ( ) is contained in the supremum of ( ) and ( ). By the

distributivity of the principal ideals there are languages ( ) ( )

such that ( ) is the supremum of ( ) and ( ).

(b) By the property of a sublattice to be a lattice it suffices to observe that for

two given countable nontrivial ideals and the classes and from (a) are

countable. The distributivity follows like in (a).

= IN and = IN (for recursive languages and )

Preliminaries

( )

( ) ( )

( )

( ) ( )

( )

2.7 Computation Trees

i j

j j

i j k

i j

fhh i i j 2 j j  j j

h i 2 () h i 2 g

\ f j 2 g

\ \ f j 2 g

fhhh i i i j 2 8 g

f j 2 g

 \ 

I J H E

z ; z ; x x C y y x

z ; y C z ; y D

I J E i

E E

I J E

I J I J E i H F

z ; z ; z ; x f x C D f

H F i

A B I A B

Theorem 2.2 (Ambos-Spies 1986)

Theorem 2.3 (Shinoda & Slaman 1990)

Proposition 2.6

exact pair theorems

For a recursively presentable ideal there

exist two recursive languages and such that ( ) ( ).

For a countable ideal there exist two

languages and such that ( ) ( ).

(a) The nontrivial countable ideals are exactly the pairwise in-

tersections of the nontrivial principal ideals. (b) The nontrivial recursively pre-

sentable ideals are exactly the pairwise intersections of the nontrivial recursively

presentable principal ideals.

the classes and from (a) are also recursively presentable. Define to

be the recursive language and for all with it

holds that . It will be shown that this construction

guarantees that = IN . The inclusion from left to right is obvious.

For the other direction consider a fixed : if is infinite, then it is also an

(infinite) language of both and , and if is finite then it is in P and therefore

in . This shows = IN . To represent the class define to

be the language ( ) , where was defined

in Section 2.3. It is easy to check that is recursive, and by construction it holds

that = IN . The distributivity follows like in (a).

The following two results – called – of Ambos-Spies in

[AS86b] and Shinoda and Slaman in [ShS90] relate the notions of ideals and prin-

cipal ideals more closely. The latter was shown to hold for the polynomial time

Turing reducibility but the proof is also valid for the many-one case.

For the nontrivial ideals the two Theorems 2.2 and 2.3 can by Proposition 2.5

be expressed the following way.

Consider nondeterministic Turing machines as presented for example in [BDG88].

In this thesis it is additionally assumed for a Turing machine that for a state and

a tupel of symbols read by the heads at most two transitions are specified by the

transition function, and also it is assumed that the transition function is given as

a linear list. This way it is guaranteed that if nondeterminism appears during a

j j

M p

M x p x

x T M ; x

computation tree

Predicate Classes and Promise Classes

16 Part I

0 1

0 1 0 0

Figure 3: Computation tree

computation the computation branches into exactly two independent computations

which can be distinguished as the left computation and the right computation.

Let a polynomial time nondeterministic Turing machine be a nondeterministic

Turing machine (of the special kind above) for which there is a polynomial

such that computes for each input on every computation path at most ( )

steps.

Let a be a – not necessarily balanced – ordered binary tree

(i. e. each inner node has a left subtree and a right subtree) where the inner nodes

have no labels, and the leaves are labeled with 0 or 1. A formal definition of

ordered trees is given for example in [HU79]. An example of a computation tree

is shown in Figure 3.

It is clear that each polynomial time nondeterministic Turing machine on

an input produces a computation tree ( ) by starting at the root, adding a

binary node – for the left and the right computation – each time a nondeterministic

branching is encountered, and writing in the case of termination a 0 (for rejecting)

or a 1 (for accepting) on the corresponding leaf.

Note that for a computation only the nondeterministic steps and the output bits

are recorded in the computation tree, not the deterministic steps and also not any

information about the configurations.

The following definition is similar to the definition of the functions in Sec-

tion 2.3. Let nondeterministic Turing machines (of the special kind above) be

coded in some straightforward way by words of . Therefore, each word can

j j

f g

2 ()

Definition 3.1

Predicate Classes

3 Predicate Classes

3.1 The Definition of Predicate Classes

x z

x i

M i

M i T M ; x T M ; x x

T  T ;



;

M L M

x L M F T M ; x :

F F L M

x L M

M x x L M

predicate class

predicate

For a predicate and a polynomial time nondeterministic Turing

machine define the language by

Let the , short , be the set of languages

for which is a polynomial time nondeterministic Turing machine.

be assumed to describe a nondeterministic Turing machine. Let be the Turing

machine which simulates on input the machine described by with the time

bound + , i.e. it cancels – with a rejecting state – on every computation path

the computation after + steps if the computation has not already terminated on

that path. Note that this enumeration (for IN) of nondeterministic Turing

machines has the following properties: is a polynomial time nondeterminis-

tic Turing machine for every , and for every polynomial time nondeterministic

Turing machine there is an such that ( ) = ( ) for all .

The following definition will be used only for examples, not for results. For

a computation tree let the rational number ( ) [0 1] be the probability to

reach a leaf with label 1 if one moves from the root of to a leaf, tossing a coin on

every inner node. For example, the computation tree in Figure 3 has the -value

In this chapter the notion of a will be defined and will be shown to

be equivalent to the notion of a principal ideal.

Let a (for computation trees) be a function from the set of computation

trees to the set 0 1 . Note that a predicate could also be considered as a tree

language.

( )

( ) ( ( )) = 1

predicate class accepted by – P ( )

In other words, membership of in ( ) is decided the following way:

construct the computation tree produced by on input , and let be in ( )

if and only if the -value of the computation tree is 1.

The following examples, especially the first, may clarify the definition above.

maj



 8 8



odd odd

a a

Predicate Classes and Promise Classes

M x L

M x x L

T M ; x

F T T

F F T

T  T > 

F T

F F T

18 Part I

Figure 4: The left and the right subtree

NP is the set of languages for which there is a polynomial time nonde-

terministic Turing machine such that if and only if there is an

accepting computation path of on input , or equivalently, if and

only if in ( ) there is a leaf with label 1. Therefore, NP is accepted by

the predicate which is 1 for a computation tree if and only if has a

leaf with label 1, in other words, NP = – P.

The class co-NP is the set of complements of languages in NP. Therefore,

co-NP is accepted by the predicate which is 1 for a computation tree if

and only if all leaves in have label 0.

P can easily be shown to be accepted by the predicate for computation

trees which is 1 if and only if the leftmost leaf in the tree has label 1.

By definition of the class P in [PZ83] it holds P = – P where ( ) =

1 if and only if for the tree the number of leaves with label 1 is odd.

By definition in [Gi77] the class PP is accepted by the predicate which is

1 for a tree if and only if ( ) , for the definition of the function

see Section 2.7. It is easy to show that PP is also accepted by the (different)

predicate which is 1 for a tree if and only if there are more leaves

with label 1 than leaves with label 0.

By the alternation characterization of PSPACE in [CKS81] one has PSPACE

= – P, where ( ) is the value of the Boolean evaluation of the formula

3 3

Σ Π ∆

Σ Σ



f g

f;g  ; f g 

F F

T F T

;

M L M F

F F

Predicate Classes

D D

D l

Proposition 3.1

Proof.

3.2 The Characterization of Predicate Classes

recursive predicates

recursive

trivial

The following sets of classes are equal: (a) the trivial predicate

classes, (b) the trivial principal ideals, (c) the trivial recursive predicate classes,

(d) the trivial recursively presentable principal ideals.

given by for which the inner nodes are alternatingly interpreted as con-

junction and disjunction gates.

The class D = NP(2), originally defined in [PY82], is the class consisting of

the languages which are an intersection of a language in NP and a language

in co-NP. The class D can easily be shown to be accepted by the following

predicate : for a single-leaf tree has the (arbitrary) value 0, and for

a non-single-leaf tree has the value 1 if and only if the left subtree

– see Figure 4 – has a leaf with label 1 and the right subtree does not have

a leaf with label 1.

The constructions in [Her92a] imply definitions for many predicates which

accept well-known complexity classes, for example the -, - and -

classes of the Polynomial Time Hierarchy.

By a usual encoding of trees into words one can consider a recursive function

on words to be a recursive function on computation trees and vice versa. Let the

set of be the set of the recursive functions from computation

trees to 0 1 and call a predicate class if it is accepted by some recursive

predicate. All examples of predicate classes given above are recursive.

Call a predicate class if it is accepted by one of the two constant predicates.

If is the constant-0 predicate then for a every polynomial time nonde-

terministic Turing machine the language ( ) is empty. Therefore, – P =

= ( ). Likewise, – P = = ( ) if is the constant-1 predicate.

This shows already the equality of the sets in (a) and (b). For (c) and (d) it suf-

fices to observe that the two trivial predicate classes are recursive and that the two

trivial principal ideals are recursively presentable.

The first main result is stated.

Theorem 3.1

Proof.

Predicate Classes and Promise Classes





f j 2 g

fh i j j j g



h i j j

h i

h i 2 ()

h i () () h i 2

f j 2 g 

F i

t i

u u

t i

u i

F u

u i

F F u F F

F F

F L M i :

F K

K z ; x; t x i F T M ; x :

F K :

K F

M y M

y z ; x; t x i

M T F T

M x t

M T M ; z ; x;

T M ; x z ; x; L M

F T M ; z ; x; F T M ; x z ; x; K

K L M K K F

F L M i K

L M F M

(a) The predicate classes are exactly the principal ideals. (b) The

recursive predicate classes are exactly the recursively presentable principal ideals.

Every predicate class is a principal ideal.

20 Part I

Note that the direction from left to right of part (a) of the theorem says that

every predicate of any recursive or non-recursive complexity accepts a complexity

class which has the ’nice’ properties of a principal ideal: with respect to it has

a complete set and is closed downward.

First part (a) with its two directions will be proven, part (b) will follow

easily.

Proof of part (a), direction :

Fix a predicate . By Proposition 3.1 it can be assumed w.l.o.g. that is not

constant-1. By the properties of the machines , see Section 2.7, one has the

following enumeration of – P :

– P = ( ) IN

For the predicate a language will be defined the following way (like this

was done for NP in [BGS75, Har78, BDG88]):

:= 0 = + and ( ( )) = 1

It will be shown that for all

– P = ( )

It will be observed first that is an element of – P : consider the following

polynomial time nondeterministic Turing machine : for an input first

checks if encodes a triple 0 with = + ; if this is not the case then

produces by nondeterminism a computation tree with ( ) = 0, otherwise

it simulates the computation of on input for steps, branching each time

branches. By construction the computation tree ( 0 ) is identi-

cal to the computation tree ( ). Therefore, 0 ( )

( ( 0 )) = 1 ( ( )) = 1 0 by

definition of . This means ( ) = and therefore – P. Now

the above equality – P = ( ) IN = ( ) is easy to see: Let

( ) be a language in – P, and remember that the running time of on

j j

Predicate Classes

j j

h i

2 

2   2

2 () 2 () 2





 2

x i

F F

F F f

x x i g x

g x z ; x;

K g L M K

L M K

B K B K f

M x f x

M f x B F

x B f x K x L M

A G

A G :

A B A g

Every principal ideal is a predicate class.

comb

word encoded by a comb

1 0

Figure 5: Comb, encoding 0001

input is bounded by + . Consider the function which for an input com-

putes in polynomial time the tripel ( ) := 0 . By the definition of

the function is a polynomial time many-one reduction from ( ) to .

Therefore, ( ) ( ). Let for the other direction of the above equation

( ), i.e. via a function FP. Then the polynomial time

nondeterministic Turing machine which for an input first computes ( )

and then runs on input ( ) shows that – P because by construction

( ) ( ). This finishes the proof of the

above equation.

Proof of part (a), direction :

Define a to be a computation tree which has the special form that the left

successor of each inner node is a leaf. The is the word

consisting of the sequence of leaf labels of these left successors of inner nodes,

starting at the top, see Figure 5.

For a language let be the predicate which is 1 for a tree if and only if the

tree is a comb which encodes a word from .

To prove that every principal ideal is a predicate class it suffices to show that

for all languages =

( ) = – P

Note that the case = is already covered by Proposition 3.1.

In order to show the inclusion from left to right of the above equation let

( ) be given, i.e. is many-one reducible to via a function FP. Now let

A A

Corollary 3.1

G g

A G A

G G

4 Promise Classes

2 () 2 () 2

2 2

2 2 () 2

2 () 2 2 

f ?g ?

4.1 The Definition of Promise Classes

Predicate Classes and Promise Classes

M x

g x

g x x B g x A x L M

B G L M G

g x L M g x A g

x M

x L M g x A L M A

F G A

; ;

The following partial orders are distributive upper semi-lattices,

the one in (b) is an upper semi-sublattice of the one in (a).

(a) The inclusion order on the set of all nontrivial predicate classes.

(b) The inclusion order on the set of all nontrivial recursive predicate classes. This

upper semi-lattice is additionally dense.

promise class

promise function promise function

22 Part I

be the polynomial time nondeterministic Turing machine which on an input

first computes ( ) and then by nondeterminism produces a comb which encodes

( ). Now of course ( ) ( ), this

means – P. For the other direction let a language ( ) – P

for a polynomial time nondeterministic Turing machine be given. A function

FP will be constructed such that ( ) ( ) . Let

be the function computed by the following polynomial time deterministic Turing

machine: on input it checks if produces a comb, note that this can be done

in deterministic polynomial time; if does not produce a comb then the machine

outputs a word not in , otherwise it outputs the word encoded by the comb. By

construction ( ) ( ) . Therefore, ( ) ( ). This

shows the above equation.

Proof of part (b).

By Propositions 2.2 and 3.1 it suffices to observe that the two constructions

in the proof of (a) keep recursiveness, i.e. the language is recursive if the

predicate is, and the predicate is recursive if the language is.

With Theorem 3.1 (and Proposition 3.1) one can immediately transfer Corol-

lary 2.2 to the predicate classes.

In this chapter the notion of a will be defined and will be shown to

be equivalent to the notion of a countable ideal.

Extend the notion of a predicate to that of a partial predicate which will be called

here: let a be a function from the set of com-

putation trees to the 3-element set 0 1 , the constant- function is excluded.

u u

6 ?

2 ()



 ?

BPP BPP

Promise Classes

Definition 4.1

Proposition 4.1

M M F F T M ; x x

M F L M

x L M F T M ; x :

F F

F L M M

M x

M x M x L

M x

F F

T T

F F T ; ;

 T ; ; ;

promise problem

For a promise function and a polynomial time nondeterministic

Turing machine say that if for all words . In

the case that respects define the language by

For every promise function define the , in short

, to be the set of languages for which is a polynomial time non-

deterministic Turing machine which respects . Call a promise class if

it is accepted by some recursive promise function.

(a) Every predicate class is a promise class. (b) Every recursive

predicate class is a recursive promise class.

This definition of a promise function can be considered as a special case of the

general concept defined in [ESY84] and [Se88].

respects ( ( )) =

( )

( ) ( ( )) = 1

promise class accepted by

– P ( )

recursive

The examples below may clarify Definition 4.1. Note that if one considers a

predicate as a promise function not having in its image then the two definitions

of – P in Definitions 3.1 and 4.1 coincide. Therefore, the following Proposition

4.1 holds.

The following examples of recursive promise classes are not known to be pred-

icate classes.

UP is the set of languages for which there is a polynomial time nondeter-

ministic Turing machine such that for every input there is at most one

accepting path of on input and (if fulfills this condition) if

and only if there is exactly one accepting path of on input . This means

that UP = – P for the promise function which has for a computation

tree the value 0 if does not have a leaf with label 1, which has the value

1 if has exactly one leaf with label 1, and which has the value otherwise.

See also [NR93] for this promise function accpeting UP.

BPP is equal to – P where ( ) has the value 0 1 or , depending

if the value of ( ) is in the interval [0 ], [ 1], or ] [, respectively.

 ?





 \

f;g f g

Proposition 4.2

Proof.

path

RP RP

H ; ;

; ; ;

F F T ;

 T ; ;

L M M

F M

T F T

F F F

Predicate Classes and Promise Classes

4.2 The Characterization of the Promise Classes

trivial

The following sets of classes are equal: (a) the trivial promise

classes, (b) the trivial ideals, (c) the trivial recursive promise classes, (d) the trivial

recursively presentable ideals.

24 Part I

Let be the promise function which has the value 0 1 or , depending if

the the quotient of the number of the leaves with label 1 and the total number

of leaves in the tree is in the interval [0 ], [ 1], or ] [, respectively.

Then accepts the class BPP defined in [HHT92]. In that paper it is

shown that it is unlikely that BPP equals BPP.

RP is equal to – P where ( ) has the value 0 1, or , depending if the

value of ( ) is 0, in the interval [ 1], or in the interval ]0 [, respectively.

FewP, defined as FNP in [Al86], is the class of languages in NP with at

most polynomially many accepting paths. FewP can be easily shown to be

accepted by the promise function which for a tree has the value 0 if there

are no leaves with label 1 in T, which has the value 1 if the number of leaves

with label 1 is 1 but does not exceed the depth of , and which has the

value otherwise.

Finite intersections of nontrivial promise classes like NP co-NP and ZPP

= RP co-RP will be shown to be promise classes in the following Lemma

4.1.

Call a promise class if it is accepted by a promise function which has not

both 0 and 1 in its image.

If a promise function does not contain 1 in its image then each language

( ) for a polynomial time nondeterministic Turing machine which respects

is empty. Such a machine always exists because it can be chosen to be the one

which computes for every input a fixed computation tree for which ( ) = 0,

remember that the constant- function was excluded to be a promise function.

Therefore, – P = . Likewise, – P = if the promise function does

not contain 0 in its image. This shows already the equality of the sets in (a) and

(

0 1

1 0

Promise Classes

D ;E

l r

D ;E

l l r

D ;E

Proposition 4.3

Proof.

Lemma 4.1

Proof.

F F F

T T

F T F T

D M M

x D D

M T T

L M D

F F

D E

T T ; T T

F T

D T D T E T

Let be a promise function. is trivial if and only if does

not have both and in its image.

(a) The intersection of two nontrivial promise classes is a nontrivial

promise class. (b) The intersection of two nontrivial recursive promise classes is

a nontrivial recursive promise class.

(b). For (c) and (d) it suffices to observe that the two trivial promise classes are

recursive and that the two trivial ideals are recursively presentable.

Note that the four sets in Proposition 4.2 above coincide with the four sets in

Proposition 3.1.

The next Proposition 4.3 is used in the proof of Lemma 4.1 and in the proof of

Theorem 4.1.

– P

0 1

The direction from right to left holds by the definition of trivial promise

classes. In order to prove the other direction it will be shown that if has both 0

and 1 in its image then it contains P: chose two computation trees and such

that ( ) = 0 and ( ) = 1 and consider a polynomial time deterministic Turing

machine . Let be the polynomial time nondeterministic Turing machine

which on input simulates , and if terminates with an accepting (rejecting)

state produces by nondeterminism the computation tree ( ). The language

( ) is by construction equal to the language accepted by . This shows that

P is contained in – P. Therefore, – P is not a trivial ideal by Proposition 4.2.

Before coming to the general characterization of promise classes the following

Lemma 4.1 is shown.

(a) Let two promise functions and be given which both have both 0

and 1 in their image. Define the following promise function : it has the value

for the two single-leaf computation trees und is determined for a non-single-leaf

tree by the left and right subtrees of (see Figure 4):

( ) := ( ) if ( ) = ( )

otherwise

For the definition of see also Figure 6.

D ;E D ;E

1 2 3 4 1 2 3 4

1 3 2 4

? ? ? ?

? ?

6 ?

()

2 \

Predicate Classes and Promise Classes

D ;E

D ;E D ;E

D ;E

D ;E l

D ;E

D ;E l l

D ;E l D l

F F

D ;E

D T

E T

F T

D E

T ; T ; T ; T D T E T D T E T

T T T T

F F

: F

F D E :

F D

M F M

x M x

M F

T M ; x

T M ; x M F

F D T M ; x D T M ; x

F T M ; x M D L M

L M L M D

F E

L D E

26 Part I

1 1

0 0

0 1

( )

Figure 6: Definition of ( )

Both and have both 0 and 1 in their image, i.e. there exist computation

trees for which ( ) = ( ) = 0 and ( ) = ( ) = 1. Then the

computation tree whose left subtree is ( ) and whose right subtree is ( ) has

the -value 0 (1). This means that has both 0 and 1 in its image, especially

it is not the constant- function. Therefore, by Proposition 4 3, – P is a

nontrivial promise class.

It will be shown that the definition of guarantees that

– P = – P – P

For the inclusion from left to right it will first be shown that each language in

– P is a language in – P. Let a polynomial time nondeterministic Turing

machine respect . Define to be the polynomial time nondeterministic

Turing machine which on input simulates the computation of on input

besides that it ignores the first branching (which exists because respects )

and only simulates the left computation. Note that the computation tree ( )

is the left subtree of ( ). Because respects it can by the definition

of be concluded that ( ( )) = and – moreover – ( ( )) =

1 ( ( )) = 1. This means that respects and ( ) =

( ). Therefore, the language ( ) is an element of – P. The same

way it is shown that each language in – P is a language in – P.

For the other direction of the equation above let a language – P – P

D ;E

2 \







Promise Classes

Theorem 4.1

Proof.

d e D d

E e d;e

e d;e D ;E

F d;e

D ;E

F f

a b

c c a

F c F a F b

M M D E L L M

L M M

x M x

M x M F

L L M L D E

D E F

F F

f L M M

F A F A L M

M x f x

M f x M F F

M ; M

M F x M M x x

M x T

F T L M L M L M

F F

I A; B I

(a) The promise classes are exactly the countable ideals. (b) The

recursive promise classes are exactly the recursively presentable ideals.

Every promise class is a countable ideal.

Every countable ideal is a promise class.

be given. This means that there are two polynomial time nondeterministic Turing

machines and respecting and , respectively, such that = ( ) =

( ). Let be the polynomial time nondeterministic Turing machine which

on input first branches and then simulates on input in the left computation

and on input in the right computation. By construction respects

and = ( ). This shows that every language – P – P is in

– P and finishes the proof of the above equation.

For part (b) it suffices to observe that if in the proof of (a) the promise functions

and are recursive then also is recursive.

The following theorem characterizes the promise classes.

First part (a) with its two directions will be proven.

Proof of part (a), direction :

Let be a promise function. By Proposition 4.2 it can w.l.o.g. be assumed that

containes 0 in its image. It will be shown that with respect to -reducibility

– P is closed downward and closed under join. To show that – P is closed

downward let a set be polynomial time many-one reducible via a reduction

function to a language ( ) where is a polynomial time nondeterministic

Turing machine which respects . Then also is in – P because = ( ),

where is the machine which for an input first computes ( ) and then simu-

lates on ( ), note that also respects . Therefore, – P is closed down-

ward with respect to -reducibility.

The closure under join is also easy to see: let be two polynomial time

nondeterministic Turing machines which respect . Then the following machine

also respects : on input 0 simulates on input , on input 1 it

simulates on input , and on the empty word as input it produces a tree for

which ( ) = 0. By construction ( ) = ( ) ( ). This shows that

the join of any two languages in – P is also a language in – P.

– P is countable because there are only countably many polynomial time

nondeterministic Turing machines.

Proof of part (a), direction :

For the two trivial ideals the statement holds by 4.2. For a given nontrivial

countable ideal let be the two languages for from the Theorem 2.3 of

( )

Predicate Classes and Promise Classes

 \ 

 

 \  \



f j 2 g

f j 2

fh i j j j  j j 6 ?g

f j 2 g f j 2 g

 f j

2 g f j 2 g





A B A

A B

F i

I A B

G G G A G B

I G G

I A B G G

F F

F L M i M F :

A A i

A z ; x F T M ; x y y x F T M ; y :

A i L M i M F :

i M F A L M

A A F L M

i M F F A i

Every recursive promise class is a recursively pre-

sentable ideal.

Every recursively presentable ideal is a recursive

promise class.

28 Part I

Slaman and Shinoda, i.e. = ( ) ( ). By Theorem 3.1 there are two

predicates and such that – P = ( ) and – P = ( ). Because

is nontrivial the two promise classes – P and – P are nontrivial promise

classes. Now by Lemma 4.1(a) also = ( ) ( ) = – P – P is a

(nontrivial) promise class.

Proof of part (b), direction :

Given a recursive promise function it is shown in part (a) that – P is an

ideal, it remains to show that – P is recursively presentable. If does not have

both 0 and 1 in its image then by Proposition 4.2 – P is a trivial recursively

presentable ideal. So it can w.l.o.g. be assumed that has both 0 and 1 in its

image. This implies by Proposition 4.3 that – P is not a trivial ideal, therefore P

– P.

First note that

– P = ( ) IN and respects

Construct – like this was done for RP and UP in [Ad78] and [AS89], respectively –

the following recursive language for which it will be shown that

IN = – P.

:= ( ( )) = 1 and for all with : ( ( )) =

It suffices to show that

IN = ( ) IN and respects

For every number IN: if respects then = ( ) by construction

of , otherwise is finite and therefore an element of P – P = ( )

IN and respects . This shows that – P = IN and finishes

the proof of part (b), direction .

Proof of part (b), direction :

The proof is analog to the one for part (a), direction , besides that Theo-

rem 2.2 of Ambos-Spies (instead of Theorem 2.3) and Lemma 4.1(b) (instead of

Lemma 4.1(a)) are used.

\ 

Promise Classes

Corollary 4.1

Corollary 4.2

4.3 Consequences of the Characterization of the Promise Classes

recursive predicate classes

recursive promise classes predicate classes

promise classes

Figure 7: The relation of predicate classes and promise classes

The following Corollary 4.1 combines Propositions 2.5 and 2.6 with Propositions

3.1 and 4.2 and Theorems 3.1 and 4.1.

The following Corollary 4.2 combines Proposition 2.4 with Theorems 3.1 and

4.1, see Figure 7.

In [Si82, Kow84, HI85, HH88, AS89] it was investigated whether promise

classes like UP, RP, BPP, and NP co-NP have -complete languages. The

(a) The nontrivial promise classes are exactly the pairwise inter-

sections of nontrivial predicate classes. The inclusion order on the set of nontriv-

ial promise classes is a distributive lattice. (b) The nontrivial recursive promise

classes are exactly the pairwise intersections of nontrivial recursive predicate

classes. The inclusion order on the set of nontrivial recursive promise classes

is a distributive lattice.

(a) The set of recursive predicate classes is a proper subset of the

set of recursive promise classes. (b) The set of recursive predicate classes is a

proper subset of the set of predicate classes. (c) The set of recursive promise

classes is a proper subset of the set of promise classes. (d) The set of predicate

classes is a proper subset of the set of promise classes. (e) There is a predicate

class which is not a recursive promise class. (f) There is a recursive promise class

which is not a predicate class.





x T M ; x

i F

Corollary 4.3

Corollary 4.4

Remark.

Predicate Classes and Promise Classes

5.1 Balanced Polynomial Time Turing Machines

5 Analogous Results for Other Nondeterministic Com-

putation Models

(a) A promise class has a -complete language if and only if it

is a predicate class. (b) A recursive promise class has a -complete language if

and only if it is a recursive predicate class.

and are recursive promise classes. is not a promise class.

corollaries

recursive

predicate classes, promise classes recursive promise classes

balanced

balanced predicate class accepted by

30 Part I

following consequence of Theorems 3.1 and 4.1 and Propositions 2.2 and 2.3 states

that this is the case if and only if the ’promise’ can be eliminated.

The next corollary follows from Theorem 4.1 and the facts stated before that

PH and BH are recursively presentable ideals and that E = DTIME(2lin) is recur-

sively presentable but not an ideal.

PH BH E

The two main results of this paper were shown in the preceeding Chapters 3 and

4. In this chapter some other models of nondeterministic computation will be

considered. For each model the notion of a predicate class is defined and an analog

of Theorem 3.1(a) is stated. The analoga will be called because their

proofs are similar to that of Theorem 3.1(a).

For the models of Sections 5.1, 5.2, and 5.3 also notions of

, and could easily be

defined in the obvious way, and analoga of Theorems 3.1(b), 4.1(a), and 4.1(b)

could be proven for each model.

Call a polynomial time nondeterministic Turing machine if for every

input the computation tree ( ) is balanced, i.e. all paths from the root of the

tree to a leaf have the same length. Note that also for this model the deterministic

steps are not recorded in the computation tree. Consider a predicate for balanced

computation trees. Note that can be characterized by a language of words of

length 2 for 1. Let the be the set of

j j

fh i j j j g

 6

f j 2 j j 0 j jg 



2 () 2

Corollary 5.1

Sketch of proof.

;

t i

;

m F

x p

5.2 Polynomial Time Bit-Reducibility

p bal

bal p bal

bal

0 1

Analogous Results for Other Nondeterministic Computation Models

L M M

x M

l T M ; x

M x M

r l

l r

M i T M ; x T M ; x x

K z ; x; t x i F T M ; x

K : A

xy x A y x A

B f ; g

x A g x; z g x; z g x; f x B ;

The balanced predicate classes are exactly the principal ideals.

bit-reducibility closures

polynomial time bit-reducible

all languages ( ) such that is a balanced polynomial time nondeterministic

Turing machine.

Let be the nondeterministic Turing machine which on

input simulates the machine in the following way: it first computes the length

of the path from the root to the leftmost leaf of ( ) and then it simulates

on input with the following two additional features: if terminates with

result on some path with length smaller than it extends by nondeterminism the

computation so that every extended path has length and result ; if on the other

side the computation is already on level of the computation tree then only the

leftmost extending computation path is simulated. The enumeration has

the property that each is a balanced nondeterministic polynomial time Tur-

ing machine, and that for each balanced nondeterministic polynomial time Turing

machine there is an such that ( ) = ( ) for all .

For a given predicate for balanced computation trees, which is not constant-

1, define the language := 0 = + and ( ( )) = 1 ,

and show – like in Theorem 3.1 – that the balanced predicate class accepted by

is equal to ( ) For the other direction define for a given language =

the predicate on balanced computation trees characterized by the language

and = 2 , and show that ( ) is equal to the balanced

predicate class accepted by .

Predicates on balanced computation trees can be identified with languages consist-

ing of words of length 2 for 1. In [HL*93, HVW94, JMT94] a certain more

general concept of balanced computation trees was introduced for which there is a

one-one correspondence between languages and predicates on balanced computa-

tion trees of that more general type. It was shown that this approach is equivalent

to the following approach of looking at .

The following definition is equivalent to the one in [HL*93]. A language is

to a language if there exist two functions FP

such that

[ ( )][ ( )] . . . [ ( ( ))]

Σ Σ

3 3

j j

0 0

Corollary 5.2

Sketch of proof.

Predicate Classes and Promise Classes

p,bit

bit

0 1

bit p,bit

0 1

bit

p,bit bit

( )

bit

i i

i j

m B m

B m

i j

t i j

i j

m m A

h x

h i

6 0 f g fh i j

j j j j 2 g

f j 2 g

 R

h i j j j j

hh i i

j j j j h i j j j j

6 f j 2 j j g

 R

 2

j j

h i 6  j j



111

bit-reducibility closure of

The bit-reducibility closures are exactly the principal ideals.

g x; z g x; z 

B B

B ;  K z ; z ; x; t

x i x j f x; z f x; z f x; f x B

f i

K B :

K B

z ; z ; x; t x i x j f x

g z ; z ; x; ; y

t x i x j g x; y y x i 

f g g w ; z g w ; z g w; f w

B f g K

B f g

A G xy x A; y

A G :

B A h f

x z i h x g

x; z  j h x j h x

 f g B

G f g

G f ; g C

A x f x

z i j

A g x; z g x; z

32 Part I

where [ ( )] is defined to be the letter 0 if ( ) = and the letter 1 other-

wise. Let ( ) be the set of all languages polynomial time bit-reducible to ,

and call ( ) the . A characterization analogous

to the one in Theorem 3.1 is obtained.

First it is indicated that every bit-reducibility closure is prin-

cipal ideal, this direction of the corollary was already shown in [BCS92]. For a

given language = let be the language 0 =

( + + ) + and [ ( )][ ( )] . . . [ ( ( ))] , remember

from Section 2.3 that FP = IN . Like in the proof of Theorem 3.1 show

that

( ) = ( )

In order to see for example that is in ( ) let f be the function which

maps an input of the form 0 where = ( + + ) + to ( ).

And let be the function which maps an input of the form 0 where

= ( + + ) + to ( ) if is not greater than + , and to

otherwise. If the input is not of that form assumed in the two definitions above,

and can be defined such that [ ( )][ ( )] . . . [ ( ( ))] is a word not

in . It is easy to see that both and are in FP and that is polynomial time

bit-reducible to via and .

In order to see that every principal ideal is a bit-reducibility closure define for

a given language = the language := = 2 . It will be

shown that

( ) = ( )

Let be -reducible to via FP. Define to be the function which maps

a word to where = ( ) + 2 . And define to be the function which

maps a pair to a (fixed) word = if ( ) and the th bit of ( ) is

1, and to otherwise. It is easy to see that both and are in FP and that is

polynomial time bit-reducible to via and . This shows the inclusion from

left to right of the above equation. In order to see the other inclusion let a language

C be polynomial time bit-reducible to via two functions FP. Then

is -reducible to via the following function in FP: on input check if ( ) is

equal to for an of the form + 2 ; if this is not the case output a word which is

not in ; otherwise output the word [ ( )] [ ( )].

∆

2 ()

T M ; x

M L M

x L M F T M ; x

F L M M

F F



Examples.

Corollary 5.3

Corollary 5.4

5.3 Polynomial Time Nondeterministic Transducers

Analogous Results for Other Nondeterministic Computation Models

polynomial time nondeterministic transducer

transducer computation trees

transducer predicate class accepted

The transducer predicate classes are exactly the principal ideals.

The following sets of classes are equal:

(a) the set of principal ideals,

(b) the set of predicate classes,

Call the following kind of polynomial time nondeterministic Turing machine a

: it is a polynomial time nondeter-

ministic Turing machine of the kind described in the introduction besides that it

outputs on each computation path not only 0 or 1 but a whole word. The compu-

tation trees ( ) of nondeterministic transducers are binary trees with words

as leaf labels. Call these trees .

Consider a predicate on transducer computation trees, and let for a poly-

nomial time nondeterministic transducer the language ( ) be defined by

( ) ( ( )) = 1. Let the

be the class of languages ( ) for which is a polynomial time nonde-

terministic transducer.

Let ( ) be the predicate which interprets for a transducer com-

putation tree the leaf labels as binary numbers and is 1 if and only if the largest

of them is odd (if and only if the largest of them appears only once in the tree).

Then – P = – P = by the results in [Wa87, Kr88] and [Pa84], respectively.

Likewise for the predicate which is 1 if and only if the length of the longest leaf

label in the transducer computation tree is odd it is easy to see that – P =

by the results in [Wa87, Kr88, Wa90].

Note that transducer predicate classes are a generalization of predicate classes:

identify all the words = . Then every predicate induces a transducer predicate –

accepting the same class – by reading as 0 and all other words as 1.

This shows already one direction of the following corollary, the other is proven

with basically the same proof as for Theorem 3.1.

Let at this point the following corollary summarize the results of Theorem

3.1(a) and Corollaries 5.1, 5.2, and 5.3.

ΣΣ

Examples.

Corollary 5.5

f g

 2

 2 2

  2 

f 2 j  g  

 

f g



5.4 Polynomial Time Function Classes

Predicate Classes and Promise Classes

m;S

F P

m;S

S S ; S S S

S S

r; t S

r t f x

r x t f x ;

t S t

r S r t t t

F S

M s M S

x F T M ; x S F F

s M M

S ;

S F

S G

(d) the set of bit-reducibility closures,

(e) the set of transducer predicate classes.

principal -ideal

-function class accepted by

The -function classes are exactly the principal -ideals.

34 Part I

Fix any nonemtpty set , for example = 0 1 , = , = IN, or = ,

and consider the set of the functions from to . Define the polynomial

time many-one reducibility among these functions, i.e. for let

if there exists a function FP such that for all :

( ) = ( ( ))

see for example [Wa86a] and also [Vo94a, Vo94b] where this reducibility is called

. It is easy to see that is a preorder. For let ( ) be the

set and call ( ) a . Note that is

-complete for ( ).

Consider a function from the computation trees to . For a polynomial time

nondeterministic Turing machine let ( ) be the function which maps

to ( ( )), and let the , in short – P, be the

set of functions ( ) such that is a polynomial time nondeterministic Turing

machine.

For = 0 1 one has exactly the case of Chapter 3. Therefore,

the concept of -function classes is a generalization of the concept of predicate

classes. For = IN let be the function which maps a computation tree to the

number of 1’s in the tree, then – P = #P according to the definition in [Va79].

For = (the set of integers) let be the function which maps a computation

tree to the difference of the number of 1’s and the number of 0’s in the tree, then

– P = GapP according to the definition in [FFK94].

With a nearly identical proof like the one for Theorem 3.1 one has for every

nonempty set the following theorem.

rel rel

h i j j



 



Sketch of proof.

Corollary 5.6

5.5 Relativized Predicate Classes

t i

m;S

F S

K z ; x; t x i

F T M ; x a S

F K

t G

T t x T x T

a S t

t G

O n H

H O n D

X X

M M

Analogous Results for Other Nondeterministic Computation Models

The -function transducer classes are exactly the principal -

ideals.

oracle polynomial time nondeterministic oracle- Turing

machine

For a function from the computation trees to define the

function which maps an input of the form 0 where = + to

( ( )), and which maps all other inputs to a fixed value which is

in the image of otherwise. It can be shown like in the proof Theorem 3.1 that

– P = ( ).

For a principal ideal -ideal ( ) let be the function which maps a

computation tree to ( ) if is a comb which encodes , and maps to a fixed

value which is in the image of otherwise. Now it can be shown like in the

proof of Theorem 3.1 that ( ) = – P.

The function class notion can be extended in the obvious way to the nonde-

terministic transducers, see the previous section. Several well-known complexity

classes are IN-function transducer classes, for example the function classes OptP

and OptP[ (log )] from Krentel [Kr88]: let be the function which interprets

for a transducer computation tree the leaf labels as binary numbers and maps the

tree to the largest number of them. Then – P = OptP by definition of OptP (for

the maximization problems), and let be the function which maps a transducer

tree to the length of the longest leaf label in the tree, then it is easy to see that

– P = OptP[ (log )]. As another example let be the function which maps

the tree to the number of its different leaf labels. Then – P = Span-P according to

the definition in [KST89]. In Vollmer’s thesis [Vo94b] several other IN-function

transducer classes are investigated. In order to get an example of a -function

transducer class let be the function which maps a transducer computation tree

to the leaf label of the leftmost path. Then – P = FP.

Again, one has the following characterization (for every nonempty set ).

Consider the well-known concept of (nondeterministic) oracle Turing machines as

described for example in [BDG88]. Let be a language, will be called in the

following context an . A

is a nondeterministic oracle Turing machine equipped with

the oracle whose running time on every path is bounded by a polynomial in the

input length (the oracle questions are counted as one step). For a computation of

j j

2 ()

j j

f j 2 g

fh i j j j g

 ! h i

Predicate Classes and Promise Classes

Example.

Corollary 5.7

Sketch of proof.

rel

rel rel

rel

rel rel

21SAT

rel

;X ;X

t i

x i

x T M ; x

T M ; x F

L M x L M

F T M ; x F

X F L M M

X X

x z

x i

X F

L M i F

K z ; x; t x i F T M ; x ;

F K x z ; x;

L M K X

X X F F

F X

P X

F X

predicate class accepted by relative to ora-

cle

Let be any language. Every predicate class relative to oracle

is a principal ideal.

36 Part I

a polynomial time nondeterministic oracle-X Turing machine on an input

the computation tree ( ) is defined like in the unrelativized case, the

oracle questions are not recorded in ( ). Given a predicate on com-

putation trees, let ( ) be the language defined by ( )

( ( )) = 1, and let the

, in short – P , be the set of languages ( ) for which is a

polynomial time nondeterministic oracle- Turing machine.

Let be the predicate accepting NP, see the first example in Section

2.5. The class is by definition the predicate class accepted by relative to

oracle SAT, in other words = – P .

Let the nondeterministic oracle Turing machines be encoded by

words. Let be the nondeterministic oracle Turing machine which simulates

on input the nondeterministic oracle Turing machine encoded by with the

time bound of + steps, note that also the oracle questions are simulated. Let

be any oracle. Like in the unrelativized case it is easy to see that – P =

( ) IN . For a non-constant predicate define like in the proof of

Theorem 3.1 the language

:= 0 = + and ( ( )) = 1

and show that – P = ( ). Note that the reduction 0

from a language ( ) to does not need the oracle .

Note that the opposite direction of the statement of the above Corollary 5.7

holds if and only if the oracle is in P: If P then – P = – P for all

predicates , so the opposite direction holds by Theorem 3.1. If does not belong

to then every predicate class relative to oracle is either trivial or it contains

the language X, so it cannot be the class P. But P is a principal ideal.

Let be the predicate from the examples in Section 2.5 which for a computa-

tion tree has the value 1 if and only if the leftmost leaf in has label 1. It is easy to

see that P = – P for every oracle , where P is the set of languages which

can be computed in deterministic polynomial time with oracle . Therefore, the

Corollary 5.8 (Ambos-Spies 1986) For every oracle the class is a princi-

pal ideal.

Analogous Results for Other Nondeterministic Computation Models

above Corollary 5.7 implies as a special case the following result of Ambos-Spies

in [AS86a] mentioned before.

38 Part I

Predicate Classes and Promise Classes

() 2

T T T

A A Y

Y T T A:

A Y

T T A

Y A

A A

regular languages

yield of

accepts

6.1 Predicate Classes Accepted by Languages

On the Acceptance Power of

Regular Languages

Part II

6 Predicate Classes Accepted by Regular Languages

In this part of the thesis predicate classes will be considered which are accepted

by a predicate of very low complexity: the predicates determined by a regular

language for the yields of computation trees.

The basic definitions and observations are presented in Chapter 6. Chapter 7

leads to a lemma about regular languages which is used in Chapter 8 to prove the

main result and its corollaries.

In Section 6.1 it will be shown how – in an obvious way – any language deter-

mines a predicate on computation trees and therefore determines a predicate class.

After the definition of in Section 6.2 some basic results about

predicate classes determined by regular languages are presented in Section 6.3.

For a computation tree let the , formally yield( ), be the word which

is the concatenation of the labels of the leaves of , read from left to right. For

example, the yield of the computation tree in Figure 3 is the word 00101100.

Given any language , one can consider as a predicate for computation

trees by the definition

( ) = 1 : yield( )

In other words, given a language , the predicate is determined for a com-

putation tree by looking at the yield of : if the yield is a word from then the

predicate has the value 1, otherwise it has the value 0.

For simplicity the predicate class – P will just be denoted as – P, this

should not cause confusion. Say that – P. Likewise denote the lan-

maj

Σ Σ

Examples.

 w w

w w w w



f g 2 !

2 

2 !

f 2 j 2 g

NP 1 1

maj

maj maj

maj

0 1

0 0

6.2 The Definition of Regular Languages

On the Acceptance Power of Regular Languages

L M M

L M

< >

F F

< >

Y F F

A Q; ; ; q ; F

Q ;  Q Q

q Q F Q

w  Q Q

  

 q   q ;  q   q ;

 A

q w  q

A Q; ; ; q ; F w  q F

finite automaton

states

transition function initial state accepting

states

language accepted by regular

40 Part II

guage ( ) (for a polynomial time nondeterministic Turing machine ) just

by ( ).

Let NP be the language which consists of the words which contain at

least one letter 1. Then obviously = where is the predicate

from Section 3.1 which accepts NP. In other words, NP – P = NP.

Likewise for the language which consists of the words which have more

1’s than 0’s it holds that = , where was one of the predicates

from Section 3.1 accepting PP. In other words, – P = PP.

In Part II of this thesis the predicate classes accepted by regular languages will

be considered. Regular languages were introduced by McCulloch and Pitts in

[MP43] and Kleene in [Kl56]. There are many equivalent characterizations of

regular languages, see for example [HU79], here they will be defined to be the

languages which are accepted by finite automata.

It follows the definition of finite automata and regular languages. To this for-

mal definition will only be refered in the proof of Lemma 7.3.

Define – like in [HU79] – a to be a quintuple = ( )

where is a finite set of , is the alphabet 0 1 , : is the

, is the , and is the set of

For every word a function : is defined the following

inductive way. Let denote the identity function, and let and be defined

by ( ) := ( ( ) 0) and ( ) := ( ( ) 1), respectively. The definition

reflects the idea that is the function which in the finite automaton starts with

a state and then follows the letters of , stopping in state ( ).

For a finite automaton = ( ) call ( ) the

. A language is called if it is accepted by a finite

automaton.

3 3

maj

Σ Σ

Σ Π

trivial

l l



; f g 0 f g

 2

   f 0 g f 0 g

f 0 g f 0 g

f g f g

R R

f j 2 Rg

Predicate Classes Accepted by Regular Languages

6.3 Predicate Classes Accepted by Regular Languages

< >

< > < >

< >

F F

< >

;  ; 

k S ; ; k <S; ; ; k >

k S

< ; ; k ; ; ; k >

< ; ; >

L L

First some examples of predicate classes accepted by regular languages will be

given:

The language NP consisting of the words which contain the letter 1 (de-

fined already in the examples of Section 6.1) is regular, i.e. NP is accepted

by the regular language NP . Note that the second example language

from Section 6.1 is not regular.

Define co-NP to be the complement of NP , i.e. the regular language

consisting of the words which only contain 0’s. By definition of co-NP the

language co-NP accepts co-NP.

Let P be the regular language which consists of the words starting with

letter 1. Then obviously = , where is the predicate from Section

3.1 which accepts P. This means P – P = P.

Call the languages which cannot distinguish any yields of computation trees

, these are the four (regular) languages , and , note

that the yield of a computation tree has at least length 1. It is easy to see

that these four languages are exactly the languages which accept the trivial

predicate classes.

In [HL*93] it is mentioned that for every IN there exist regular languages

accepting the classes and of the Polynomial Time Hierarchy. Also

there the existence of a regular language accepting the class PSPACE is

shown.

For a number 2 and a subset 0 . . . 1 let 0 . . . 1

be the regular language consisting of the words for which the number of 1’s

is equal modulo to an element of . Then, by definition of MOD P, see

[BG92], the language 1 . . . 1 0 . . . 1 accepts the predi-

cate class MOD P. As a special case, the language 1 0 1 accepts

by definition P.

Let be the set of all nontrivial regular languages, and let – P be the set of

classes – P , i.e. the set of all predicate classes which are accepted by

a nontrivial regular language.

A A B

A B

0 0

1 2

8 [

 8

2 () 2 () 2

 8

 2 62

2 2

On the Acceptance Power of Regular Languages

Theorem 6.1 ([HL*93])

Remark.

Proposition 6.1

Proof.

A; B A B A B

A B A B

A A B

M M

M x

T M ; x A T M ; x A T M ; x

A B x

M L M L M A A B

B A B

A B

A B C

A B

M L M

L M C v ; w

v C w C

M M M

x M x

M M M

v  A  B w

P is the minimum of the inclusion order on , and

is its maximum .

The inclusion order on is an upper semi-lattice.

42 Part II

The following Theorem 6.1 is due to Hertrampf, Lautemann, Schwentick, Voll-

mer and Wagner in [HL*93].

– P

PSPACE

Note that it is not known whether P = PSPACE. In that case – P

would – by the above theorem – only consist of the class P, and the following

Proposition 6.1 and even Theorem 8.1 in Chapter 8 would hold for trivial reasons.

– P

Given two languages , let be the language 0 1 . It will

be shown that – P is the smallest class containing both – P and – P.

In order to show that – P – P let a polynomial time nondeter-

ministic Turing machine be given. Define to be the polynomial time non-

deterministic Turing machine which on input first produces by nondetermin-

ism a 0 in the leftmost path, and then simulates on input . By construction

yield( ( )) yield( ( )) 0 yield( ( ))

for all inputs . In other words, for every polynomial time nondeterminis-

tic Turing machine there is polynomial time nondeterministic Turing machine

such that ( ) = ( ). Therefore, – P – P. The inclusion

– P – P holds similarly.

In order to show that – P is the smallest class among the predicate classes

accepted by nontrivial regular languages containing both – P and – P let – P

be another nontrivial (regular) language containing – P and – P. It will be

shown that for every polynomial time nondeterministic Turing machine there

is polynomial time nondeterministic Turing machine such that ( ) =

( ). Because is not trivial one can choose two words with length

1 such that and . Given a polynomial time nondeterministic

Turing machine , define ( ) to be the polynomial time nondeterministic

Turing machine which for an input first checks if on input has more than

one computation path. If yes then ( ) simulates besides that it does not

compute the leftmost path; otherwise it produces by nondeterminism a computa-

tion tree with yield if ( ) and a computation tree with yield if

A B C

Definition 7.1

3 4 1

3 2 4

3 4

0 0

7.1 o-h-Reducibility

62 62

() 2 2 () 2

2 8 () 2

8 

2 () 2

A Lemma about Regular Languages

7 A Lemma about Regular Languages

 A  B C A B

M M M ; x

A M ; x C M ; x B M ; x C

M M M

M ; x A B M ; x C

M L M L M

A B C

 h



h   h ax h a h x a x

A B

A; B A B

y ; z  h

x A y h x z B :

generalized definite languages

-free homomorphism

o-h-reducibility

offset–homomorphism

Let be two languages. is to if there exist

two words , called the , and an -free homomorphism such that for all

words

( ). Because – P contains both – P and – P there exist polyno-

mial time nondeterministic Turing machines and such that yield( )

yield( ) , and yield( ) yield( ) , re-

spectively. Now let be the polynomial time nondeterministic Turing machine

which for an input first looks if the bit of the leftmost path of the computation

of on the input is 0 or 1 and then simulates or , respectively. By con-

struction is yield( ) yield( ) . In other words, for

every polynomial time nondeterministic Turing machine there is polynomial

time nondeterministic Turing machine such that ( ) = ( ). This

shows – P – P.

It will be shown in Chapter 8 that if a nontrivial regular language does not

accept P then at least one of the classes NP, co-NP or MOD P for prime is

contained in – P. For the proof the following detour to formal languages will be

made.

In Section 7.1 a reducibility among languages will be introduced which implies

the inclusion of the corresponding accepted predicate classes. It will be shown in

Section 7.3 that for the regular languages this reducibility is related to the concept

of which will be defined in Section 7.2 .

Let an be a mapping which maps the letters 0 and 1 to

non-empty words. An ( -free) homomorphism is extended to words inductively

by ( ) := and ( ) := ( ) ( ) for a letter and a word , see also [HU79].

For two languages and the will be defined, the name

stands for . It is not known to the author whether the concept

is defined in the literature.

o-h-reducible

offsets

( )

A B

2 () 2 ()



2 () 2



  f 0 g

f 0 g

On the Acceptance Power of Regular Languages

1 1

2 2 2

2 2 1 2 1 2 2 1

2 1 1 1 1

2 2 1 2 1 2 1 2 1 2

0 0

1 2

Proposition 7.1

Proof.

Lemma 7.1

Proof.

Example.

The o-h-reducibility on the set of all languages is a preorder.

Let be languages. If is o-h-reducible to then

id id id

A B y z

h B C

y z h A C

y h y h z z h h h h

h h h x A y h x z B

y h y h h x h z z C h  h h

A; B A B A

A B y z

h M

L M L M x M M x

y z M

y z T M ; x A T M ; x B

A B

L L

L id id ; id

y z  L L

k S ; ; k

<S; ; ; k >

44 Part II

A language is o-h-reducible to itself via two empty offsets and the ho-

momorphism with (0) = 0 and (1) = 1. This shows the reflexivity of the

relation, the transitivity is also shown in a straightforward way as follows. Let

a language be o-h-reducible to a language via the offsets and and the

homomorphism determined by , and let be o-h-reducible to a language via

the offsets and and the homomorphism . Then is o-h-reducible to via

the offsets ( ) and ( ) and the homomorphism with (0) = ( (0))

and (1) = ( (1)) because it holds ( )

( ) ( ( )) ( ) . Finally note that is -free because and

are.

The following easy lemma motivates the definition o-h-reducibility.

– P

Let be o-h-reducible to via the offsets and and the homomor-

phism . For a given polynomial time nondeterministic Turing machine a poly-

nomial time nondeterministic Turing machine will be constructed such that

( ) = ( ). On input simulates the computation of on input ,

producing everytime rejects or accepts by nondeterminism a computation tree

whose yield is h(0) or h(1), respectively. And if ( ) is not the empty word,

produces additionally in the leftmost (rightmost) computation path a tree whose

yield is ( ). By construction yield( ( )) yield( ( )) .

This shows – P – P.

Let, like in [BGu82, GW87], 1–NP (2–NP) be the class accepted by

the regular language ( ) which consists of the words which contain exactly

one 1 (exactly two 1’s). The lemma above shows that 1–NP 2–NP because

is o-h-reducible to via the homomorphism with (0) = 0 (1) = 1 and the

offsets = 1 and = . The languages and also show that the opposite

direction of the Lemma 7.1 above does not hold because it is easy to see that is

not o-h-reducible to but 1–NP = 2–NP was shown in [GW87].

Remember that for a number 2 and a subset 0 . . . 1 the

language 0 . . . 1 was defined (in the last example of Section 6.3) to

1 1

0 0

n i i

Lemma 7.2

Proof.

A Lemma about Regular Languages

For a nonemtpty set for some there exists

a prime and a nonempty set such that

is o-h-reducible to .

f 0 g

f 0 g 



 f 0 g 

 f 0 g f 0 g

f 0 g

f 0 g f 0 g

f 0 0 0 0 g

2 f 0 g \

 f 0 g f j

2 \ g f 0 g

f 0 g

f 0 g 2 f 0 g () 2

\ f 0 g 2 f 0 g ()

2 f 0 g

2 f 0 g \

\ f 0 g

f 0 g f 0

g 2

f 0 g f 0 g

 f 0 g

f 0 g f 0 g

k S S ; ; k

<S; ; ; k >

S ; ; k k

p Q ; ; p <Q; ; ; p >

<S; ; ; k >

k k

Q S k mn < m; n < k U

; n; n; ; m n ; U ; n ; n ; ; m n ; ; ; U

n ; n ; n ; ; mn

i ; n S U

U Q ; ; m Q j

j n i S U <Q ; ; ; m >

<S; ; ; k > h

h ; h  h x

<U ; ; ; k > x x <Q ; ; ; m > h x

h x <S; ; ; k >

i ; n S U

U j j k

S j n k S

Q S ; ; n Q

; ; n S ; ; k

j j

n Q j k

S <Q ; ; ; n > <S; ; ; k >

p Q ; ; p

<Q; ; ; p > <S; ; ; k >

be the regular language consisting of the words for which the number of 1’s is equal

modulo to an element of . Note that if is empty or equal to 0 . . . 1 then

0 . . . 1 is trivial. The following Lemma 7.2 gives some examples

of o-h-reducibility among the languages of the type 0 . . . 1 where

is a nonempty and proper subset of 0 . . . 1 for some 2. The relation

of being a proper subset will be expressed in the following text by .

0 . . . 1 2

0 . . . 1 0 . . . 1

0 . . . 1

The proof is by induction on the factorization length of . If is a prime

then take := . If = for 1 then consider the sets :=

0 2 . . . ( 1) := 1 + 1 2 + 1 . . . ( 1) + 1 . . . :=

1 2 1 3 1 . . . 1 . Two cases (1) and (2) are distinguished:

(1) Assume that for some one 0 . . . 1 the set is neither empty

nor equal to . Define the nonempty set 0 . . . 1 by :=

+ . Now the language 0 . . . 1 is o-h-reducible

to the language 0 . . . 1 via the homomorphism determined by

(0) := 0 (1) := 1 and the offsets 1 and : it is easy to see that 1 ( )

0 . . . 1 for all , and that 0 . . . 1 1 ( )

0 . . . 1 , this means that 0 . . . 1

1 ( ) 0 . . . 1 .

(2) Assume that for all 0 . . . 1 the set is either empty

or equal to . Then for all numbers IN it holds: modulo is equal to

a number in if and only if + modulo is equal to a number in . Let

be the set 0 . . . 1 . Note that is a nonempty and proper sub-

set of 0 . . . 1 because is a nonempty and proper subset of 0 . . .

1 . Now it is easy to see that for all numbers IN it holds that modulo

is equal to a number in if and only if modulo is equal to a number in

, in other words: 0 . . . 1 = 0 . . . 1 . Therefore,

0 . . . 1 is o-h-reducible to 0 . . . 1 by the reflexivity

of the o-h-reducibility.

In both cases (1) and (2) there exists by the induction assumption and by the

transitivity of the o-h-reducibility a prime and a nonempty set 0 . . . 1

such that 0 . . . 1 is o-h-reducible to 0 . . . 1 .

0 2

0 1

0 0 0

n n n n

n n n n n n

n n

2 () 2



f 0 g  f 0 g 

f 0 g

 f 0 g

)



On the Acceptance Power of Regular Languages

Definition 7.2 (Eilenberg 1976)

Lemma 7.3

Proof.

7.2 Generalized Definite Languages

7.3 The Main Lemma

n x; y n

v ; w

xv y L xw y L:

n L z n

z n

< >

< > < >

<S; ; ; k > S ; ; k k

< > < > <Q; ; ; p >

Q ; ; p p R

< >

R z ; z  h h

w h w n

< > < >

z h z z h w h z R z h w h z

R z h h z n

n R < >

Call a language if there

is a natural number such that for all words of length and for all words

(of any length) it holds

A regular language is generalized definite if and only if none of

the languages , , and for a nonempty set

for a prime is o-h-reducible to .

46 Part II

The following concept is defined implicitly in Eilenberg [Ei76], see also [Heu89].

generalized definite

In other words, a language is generalized definite if and only if there is a

number such that the membership in for a word which has length 2

depends only on the prefix and the suffix of of length .

The finite and the cofinite languages are examples of generalized definite lan-

guages. The language P , which was defined to consist of the words start-

ing with letter 1, is an example of a generalized definite language which is nei-

ther finite nor cofinite. Note that a generalized definite language is a regular

language, but for example none of the regular languages NP , co-NP and

0 . . . 1 for a nonempty set 0 . . . 1 for 2 is gener-

alized definite.

The following Lemma 7.3 is a lemma about regular languages, independent of

questions about polynomial time computations.

NP co-NP 0 . . . 1

0 . . . 1

To see the direction = let NP be o-h-reducible to a (regular) lan-

guage via two offsets and an -free homomorphism determined by (0) =

and (1) = . Given IN, consider the words 0 00 and 0 10 . Because

the first word is not in NP and the second is in NP one has by the o-h-

reducibility that (0 00 ) = (0 ) (0 ) is not in and (0 ) (0 )

is in . But the length of (0 ) and the length of (0 ) are both . Be-

cause this holds for every IN is not generalized definite. For co-NP and

reachable

1 2 1 2 1

3 3

j j 0 j j

0 0

1 +1

1 2 3 1 2 3 2

1 1

0 2

A Lemma about Regular Languages

m n

i w i m w n

z m z n

z j z m

z m z n

Q Q

s s s s s

m n us

s m s n

j m s j

z j

f 0 g  f 0 g

f g

 



f g

n f 0 g

 f 0 g

0  f 0 g

f 0 j   2 g

2 f 0 g () 2

f 0 g

 f 0 g

f g n

j j 2 62 j j

! 6

f 2 j 9 2 g

2 f g

<Q; ; ; p > Q ; ; p p

< > < >

<Q; ; ; p > Q ; ; p p

R Q; ; ; ; q ; F

 Q Q

q q Q w  q q

Q w q 

q w

q m n c ; ; c ; ; c

c q c  c i < n c  c

z  c ; ;  c F

Q F <Q; ; ; p >

Q ; ; p p R

k n m S ; ; k

j m m j n  c F z  q c

h h w h w

x x <S; ; ; k > z h x z R

<S; ; ; k > R

<Q; ; ; p >

Q ; ; p p R

q w ; z

 c  c F Q F

R r; s; t; t r

s Q r ts R r t s R Q

Q Q s ; s ; s s s s s s 

   q Q q Q q  q



u q  c ; ;

c ; ; c  q c

 c ; ;  c F Q F

c c ; ; c  c F

z  q c h h s

0 . . . 1 for a nonempty set 0 . . . 1 with prime the

proof is analog.

For the other direction of the lemma assume that a regular language is not

generalized definite. It will be shown that one of the languages NP , co-NP ,

or 0 . . . 1 for a nonempty set 0 . . . 1 for a prime is

o-h-reducible to .

Let be accepted by the finite automaton ( 0 1 ). For the defi-

nition of a finite automaton and the definition of the function : (for

every word ) see Section 6.2. Assume w.l.o.g. that every state is reachable from

, i.e. for every state there is a word such that ( ) = .

Because is finite, for every word and every state the iteration of start-

ing in state has to run into a cycle sometime, more formally: for every word

and every state there exist two numbers 1 such that . . . . . .

are different states, = , = ( ) for 1 and = ( ). Assume

that for some other word the set ( ) . . . ( ) has elements from both

and . It is shown that in this case a language of the type 0 . . . 1

for a nonempty set 0 . . . 1 for some prime is o-h-reducible to :

let := 1 + and define the nonempty set 0 . . . 1 to be the set

and ( ) . Take a word for which ( ) = .

Define the homomorphism by (0) = and (1) = . Now it is clear that for

every word : 0 . . . 1 ( ) , this means that

the language 0 . . . 1 is o-h-reducible to , and by Lemma 7.2 and

the transitivity of the o-h-reducibility also a language 0 . . . 1 for a

nonempty set 0 . . . 1 for some prime is o-h-reducible to .

From now on assume that for all states and for all words like above the

set ( ), . . ., ( ) consists of states which are either all in or all in .

Because is not generalized definite there exist words such that and

have length and but . There are at most mappings

. Therefore, there exist words such that = , = and

= , i.e. is the identity function on the set : = ( )

- the set of states by .

Consider for some word and a state reachable by the set of states . . .

. . . of the iteration of starting with = . By assumption the states

( ) . . . ( ) do belong either all to or all to . Consider the first case

and assume that for some . . . the state ( ) is not in . Then,

taking a word for which ( ) = and defining a homomorphism by (0) =

0 0

a a

8.1 The Main Result

3 3

3 1 3

1 1 2

1 1 3 1 3 1 3

1 1 3

1 3 1 3 3 1 3 1

Lemma 8.1 (Beigel & Gill 1992)

Proof.

On the Acceptance Power of Regular Languages

For a prime and a nonempty set

the language accepts .

8 A Result for Classes Accepted by Regular Lan-

guages

1 3

1 1

1 2 3 1 2 3 2

0 0 2 3 1

1 3

(0 1) 0

(0 1) 0 0 0

3 (0 1) 0 (0 1 ) 0

(0 1) ( ) 0 ( ) (0 1) 0

f g 2 () 2

2 f g

2 () 2

2 62

 j j 6

2 () 2

( ) 2

 f 0

g f 0 g

 f 0 g

f 0 g f 0 g

f 0 g f 0 g f 0 g

s m s n j m

s j

s us s

r r r

r h

s r h s r r ts s r ts

r h r h y r t s

r h h y r t s s h y r t s s r h

h us x < > z h x s R

< > R < > R

 c ; ;  c F c c ; ; c

 c F

u q 

 q F  q F

r r ts R r t s R r

Q r ; r ; r r r r r r 

 q  q h h r h r ts

x < > r h x r t s R < >

R x

< > x y a  q

  q  q  q F

u h y r t q  q  q

 q   q F

p Q ; ; p

<Q; ; ; p >

Q ; ; p

< ; p ; ; ; p >

<Q; ; ; p > < ; p ; ; ; p >

48 Part II

and (1) = , it is easy to see that NP ( ) , i.e.

NP is o-h-reducible to . Likewise, co-NP is o-h-reducible to if none of

the states ( ) . . . ( ) is in and there is some . . . such

that ( ) is in .

So the only case left is that for each word and each state reachable by

the following holds: ( ) ( ) .

Take the word from above for which but . Because has

length there exist three words such that = , = and

( ) = ( ). Define the homomorphism by (0) = and (1) = .

It will be shown that NP ( ) , i.e. NP is o-h–

reducible to . The implication is obvious, and for consider a word

NP , i.e. = 0 1 for some IN. Then the state ( ) is reachable

by and ( ) = ( ) = ( ) . Therefore, by the above

assumption applied to = ( ) and = ( ) also ( ) =

( ) = ( ( )) .

In Section 8.1 the main result of Part II is presented. The Sections 8.2 and 8.3 will

interpret the main result as a non-density result. In Section 8.4 the analog of the

main result is shown for the log-space case.

First the following Lemma 8.1 is shown which can be considered as an easy con-

sequence of the results and methods of Beigel and Gill in [BG92].

0 . . .

1 0 . . . 1 MOD P

The results and methods of [BG92] are applied. Fix a prime and a

nonempty set 0 . . . 1 . Because MOD P is by definition equal to

1 . . . 1 0 . . . 1 – P it needs to be proven:

0 . . . 1 – P = 1 . . . 1 0 . . . 1 – P

1 1

Theorem 8.1

Proof.

f g f 0

0 0

f 0 g  f 0 g f 0 g

2 2 f 0 g n

f 0 g f 0 g 

f 0 g







A Result for Classes Accepted by Regular Languages

Let be a nontrivial regular language. If is generalized definite

then , otherwise contains at least one of the classes , , or

for prime.

i ; ; i ; ; p

Q M

M x a p i a p

i a p i M a x p

x M p

Q M p

<Q; ; ; p > < ; p ; ; ; p >

i Q j ; ; p Q

M M

M x p

i j i M

x p < ; p ; ; ; p >

<Q; ; ; p >

A A

n A

n A A

M L M

A n D

A n x D

n T M ; x

T M ; x M D

T M ; x < n

T M ; x

A D T M ; x n

v n T M ; x

n T M ; x w n

T M ; x D v w

To show the inclusion from left to right let . . . be the numbers in 0 . . .

1 which are not in . Given a nondeterministic machine construct by Prop-

erty 2.2. of [BG92] the machine which for an input has ( + )( +

) . . . ( + ) accepting paths if has accepting paths on input . Because

is prime for every input the number of accepting paths of is equal modulo to

an element of iff the number of accepting paths of is not equal modulo to

0. Therefore, 0 . . . 1 – P 1 . . . 1 0 . . . 1 – P.

For the inclusion from right to left let and 0 . . . 1 . Then by

Theorem 6.3. of [BG92] there is for every machine a machine such that the

number of accepting paths of on an input is always equal modulo to either

or and it is equal to if and only if the number of accepting paths of on input

is not equal modulo to 0. Therefore, 1 . . . 1 0 . . . 1 – P

0 . . . 1 – P.

Now the main result is stated.

– P = P – P NP co-NP

MOD P

Consider a nontrivial regular language . Assume that is generalized

definite, and let the number be the constant for from Definition 7.2, i.e. for a

word with length 2 membership in depends only on its prefix and its suffix

of length . It will be shown that accepts P. P is of course a subset of – P, and

in order to see that – P is a subset of P let a polynomial time nondeterministic

Turing machine be given. It suffices to show that ( ) is in P. Consider

the following deterministic Turing machine which works in polynomial time.

Because is fixed and is constant it can be assumed that has a list of all words

in of length 2 . For an input the machine first visits by a left traversal (see

for example [AHU74]) deterministicly the 2 leftmost leaves of ( ), note that

the left traversal of ( ) can be done by simulating . If recognizes that

the yield of ( ) has length 2 then it terminates, and it terminates with

an accepting state if and only if it finds the yield of ( ) in its list of words

belonging to . If recognizes that the yield of ( ) has length 2 it

memorizes the prefix of length of the yield of ( ), and visits with a right

traversal the rightmost leaves of ( ) in order to find the suffix of length

of the yield of ( ). Finally, looks up in its list whether the concatenation

Σ Σ

f 0 g

 f 0 g

f 0 g

 f 0 g

8 

1 1

 1 8  1 

On the Acceptance Power of Regular Languages

Corollary 8.1

Lemma 8.2 (Toda 1991)

Sketch of proof.

8.2 A Non-Density Result on the Assumption that PH does not

Collapse

A D x

T M ; x A D L M

L M

M A

< > < > <Q; ; ; p >

Q ; ; p p A

< > < > <Q; ; ; p >

Q ; ; p p A

A A

A p

generalized definite

Let be a nontrivial regular language. If is not equal to

then contains at least one of the classes , , or for prime.

collapses to collapses

If for some prime is contained in or

then PH collapses to .

50 Part II

belongs to , and accepts if and only if this is the case. By construction and by the

property of to be generalized definite it follows that accepts the input if and

only if the yield of ( ) is in . In other words, accepts ( ). This shows

that ( ) is in P. Because this holds for every polynomial time nondeterministic

Turing machine the class – P is a subset of P.

If on the other hand is not generalized definite then by Lemma 7.3 at least one

of the languages NP , co-NP or 0 . . . 1 for a nonempty set

0 . . . 1 for a prime is o-h-reducible to . Therefore, by Lemma 7.1 at

least one of the classes NP – P = NP, co-NP – P = co-NP or 0 . . . 1 – P

for a nonempty set 0 . . . 1 for a prime is contained in – P. By

Lemma 8.1, at least one of the classes NP, co-NP, or MOD P is contained in – P.

The theorem can be stated in the following weaker form in which the notion

is not used.

– P P

– P NP co-NP MOD P

Remember that PH is the union of the classes of the Polynomial Time Hierarchy.

Say that PH if PH = , and say that PH if there is some

IN such that PH collapses to .

The following Lemma 8.2 can be seen as an easy consequence of the results

of Toda in [To91].

MOD P NP co-NP

Consider the case = 2. Assuming P NP one has with the

notation of [KST93] (BP is the operator corresponding to BPP, i.e. BP P = BPP):

PH BP P BP NP

8 

2 R

Π Σ

Σ Σ

2 2

L L

p L

A X A

p p

Corollary 8.2

Proof.

8.3 A Non-Density Result for the Relativized Case

A Result for Classes Accepted by Regular Languages

If PH does not collapse (to ) then and are two atoms

of the inclusion order on .

family

The first inclusion holds by a result in [To91], the second inclusion holds by the

assumption, and the third inclusion holds by a result in [Ba85]. Therefore, PH =

= . The same argumentation goes through for primes = 2, see [TO92].

Because MOD P is closed under complements, see [BG92], the lemma also holds

for the assumption P co-NP.

The assumption that PH does not collapse is stronger than the assumption

P = NP but still can be considered reasonable. The next corollary states that a

nondensity-result would follow as a consequence.

NP co-NP

– P

First note that if PH does not collapse (to ) then P, NP, and co-NP are

different from each other. Now assume that a class – P for a language

is properly between P and NP. Because in that case – P is not equal to P the

class – P contains, by the previous Theorem 8.1, one of the classes NP, co-NP,

MOD P for prime. By the assumption – P cannot contain NP, and also it cannot

contain co-NP, because then NP would properly contain its set of complements,

a set-theoretic contradiction. So the only case left is that – P contains a class

MOD P for prime. But then also NP contains MOD P, and PH collapses to by

the previous Lemma 8.2. This shows that if PH does not collapse (to ) then there

cannot be a class in – P properly between P and NP. The same argumentation

holds for co-NP.

Consider the relativized versions of the classes and of the Polynomial Time

Hierarchy. For all oracles the first class is a subset of the second but there is an

oracle for which this inclusion is proper, see [BGS75, St77, Has86]. The same

holds for the relativized versions of many pairs of complexity classes. This concept

of comparing complexity classes was formalized by Zachos in [Za88] to define a

partial order on relativizable complexity classes which expresses that an inclusion

is oracle independent. This concept will be presented now.

Obviously the definitions of Section 6.1 can be relativized for every oracle ,

see Section 5.5. This way for each language and each oracle the class – P

is defined. Let a be a mapping from the set of oracles to classes. Families

Σ Σ Σ

Σ Σ

! !

 !

! R

! 2

! R

A A A

A; B A B

A B X

A B

p q X

On the Acceptance Power of Regular Languages

Proposition 8.1

Proof.

Corollary 8.3

Proof.

X X

p; X

X X

( )

( ) ( )

( )

( ) ( ) ( )

( ) ( )

+1 ( )

( )

( ) ( ) ( )

( ) ( )

( )

accepts the family

The partial order on is an upper semi–lattice which

has a minimum, a maximum, an infinite chain and an infinite antichain.

corollary

The upper semi-lattice on is atomic. The atoms are the

pairwise different families , and for prime.

52 Part II

will be indicated by parenthesis around the oracle variable, for example the family

which maps an oracle to the class NP will just be denoted by NP . This

way each language defines the family – P , say that

– P

On the set of families accepted by nontrivial regular languages the partial order

will be defined. Let be two languages, define – P – P if

– P – P holds for every oracle . The partial order corresponds to

the idea of oracle independent inclusion of relativizable complexity classes. The

concept and the symbol is the same as the one of Zachos in [Za88] though here

the definition is for families instead of classes.

Let – P be the set of families which are accepted by a nontrivial regular

language.

– P

The upper semi-lattice part holds by the oracle-independent construction

of in the proof of Proposition 6.1. The minimum and maximum are P

and PSPACE , respectively, by Theorem 6.1 which is relativizable. The chain is

given by the families because was shown for every IN

in [St77], and = by the results in [BGS75, Has86]. To obtain an

antichain consider the families MOD P for prime: by a result in [BG92] there

exists for any two primes = an oracle such that MOD P is not a subset of

MOD P , what is another way of saying that the families MOD P for prime

are pairwise –incomparable.

A natural question for a given partial order is to ask about density, see for

example [La75]. The following result says that the partial order on – P

is atomic and therefore not dense, see Figure 8.3. The result is called ˚

because its proof is nearly the same as the proof of Theorem 8.1.

– P

NP co-NP MOD P

By the results in [BGS75, Yao85, Bei91, Tor91] the families NP , co-NP

and MOD P for prime are pairwise incomparable and therefore they are dif-

ferent from P . The corollary is now proven by a relativized version of the proof

of Theorem 8.1.

1 j j

X X

X X X

( )

( ) ( ) 2( ) 3( ) 5( )

( )

c x

T M ; x x L M

F F L M M

8.4 An Analogous Result for the Log-Space Case

A Result for Classes Accepted by Regular Languages



log-space nondeterministic Turing machine

log-space predicate class

accepted by

Figure 8: shown as a diagram

NP co-NP MOD P MOD P MOD P . . .

inside the triangle: the other families of – P

PSPACE

Let a be a nondeterministic Turing

machine (of the kind described in the introduction) for which there is a constant

such that for an input the computation terminates on every path and does not

use more than log ( ) cells of the working tape on every path. Because ev-

ery log-space nondeterministic Turing machine is a polynomial time one, the

computation tree ( ) for an input and the language ( ) for a predi-

cate on computation trees is already defined. Let the

, in short – L, be the set of languages ( ) such that is a

log-space nondeterministic Turing machine. Let – L be the log-space predicate

class accepted by .

With identical proofs the Lemmata 7.1 and 8.1 have their following analoga 8.3

and 8.4 for the log-space case. For the proof of Lemma 8.4 results from [BD*92]

(instead from [BG92]) are applied.



 f 0 g

f 0 g

A; B A B A

Q ; ; p p

<Q; ; ; p >

A A

A p

n n

On the Acceptance Power of Regular Languages

Lemma 8.3

Lemma 8.4

Corollary 8.4

Sketch of proof.

Let be two languages. If is o-h-reducible to then

For a nonempty set for a prime the language

accepts .

Let be a nontrivial regular language. If is not equal to

then contains at least one of the classes or for prime.

54 Part II

– L

0 . . . 1

0 . . . 1 MOD L

The following corollary is the log-space analog of Theorem 8.1, it is stated in

the form of Corollary 8.1.

– L L

– L NL MOD L

The proof is basically the same as the one for 8.1. If is

generalized definite then it follows – L = L with the analog argumentation like

in the proof of Theorem 8.1, besides that the left and the right traversal algorithm

have to be done with a look-ahead of 2 and nodes, respectively.

If is not generalized definite then the same argumentation with Lemma 7.3

applies like in the proof of Theorem 8.1, using Lemmata 8.3 and 8.4. Additionally

it is known from [Im88, Sz88] that NL = co-NL.

References

Two theorems on random polynomial time

The Design and Analysis of

Computer Algorithms

The complexity of sparse sets in P

On the structure of the polynomial time degrees of

recursive sets

Sublattices of the polynomial time degrees

A note on complete problems for complexity

classes

Minimal pairs for polynomial time reducibilities

On the relative complexity of hard problems for

complexity classes without complete problems

Trading group theory for randomness

Relativizations of the P=NP? question

Structural Complexity I

Relativized counting classes: relations among thresholds,

parity and mods

[Ad78] L. Adleman. , Proc. 19th

IEEE Symp. on Foundations of Computer Science, 1978, pp. 75–83

[AHU74] A. V. Aho, J. E. Hopcroft, J. D. Ullman.

, Addison-Wesley, Reading, MA, 1974

[Al86] E. W. Allender. , 1st Structure in

Complexity Theory Conference, Lecture Notes in Computer Science

223, Springer Verlag, 1986, pp. 1-11

[AS85a] K. Ambos-Spies.

, Habilitationsschrift, Universit¨

at Dortmund, 1985

[AS85b] K. Ambos-Spies. , Infor-

mation and Control , 1985, pp. 63–84

[AS86a] K. Ambos-Spies.

, Information Processing Letters , 1986, pp. 227–230

[AS86b] K. Ambos-Spies. ,

Computation Theory and Logic, Lecture Notes in Computer Science

270, Springer Verlag, 1986, pp. 1–13

[AS89] K. Ambos-Spies.

, Theoretical Com-

puter Science , 1989, pp. 43–61

[Ba85] L. Babai. , Proceedings of the

17th ACM Symposion on Theory of Computing, 1985, pp. 421–429

[BGS75] T. Baker, J. Gill, R. Solovay. ,

SIAM Journal of Computing , 1975, pp. 431–442

[BDG88] J. Balcazar, J. Diaz, J. Gabarro. , Springer

Verlag, 1988

[Bei91] R.Beigel.

, Journal of Computer and System Science , 1991,

pp. 76–96

References

103

104

Counting Classes: thresholds parity, mods, and

fewness

On the unique satisfiability problem

On the acceptance power of regular languages

Predicate classes and promise classes

Complexity classes and sparse

oracles

A uniform approach to de-

fine complexity classes

Structure and

importance of logspace-MOD classes

The Boolean Hierarchy 1:

structural properties

Alternation

The complexity of theorem proving procedures

Automata, languages, and machines

[BG92] R. Beigel, J. Gill.

, Theoretical Computer Science , 1992, pp. 3–23

[BGu82] A. Blass, Y. Gurevich. , Infor-

mation and Control , 1982, pp. 80–88

[Bo94a] B. Borchert. ,

Proc. 11th Symposium on Theoretical Aspects of Computer Science

(STACS), Lecture Notes in Computer Science 775, Springer Verlag,

1994, pp. 533–542

[Bo94b] B. Borchert. , Proc. 9th Struc-

ture in Complexity Theory Conference, 1994, pp. 235–241

[BCS91] D. P. Bovet, P. Crescenzi, R. Silvestri.

, Proc. 6th IEEE Structure in Complexity Theory Conference,

1991, pp. 102–108

[BCS92] D. P. Bovet, P. Crescenzi, R. Silvestri.

, Theoretical Computer Science , 1992,

pp. 263–283

[BD*92] G. Buntrock, C. Damm, U. Hertrampf, C. Meinel.

, Mathematical Systems The-

ory , 1992, pp. 223–237

[CG*88] J. Y. Cai, Th. Gundermann, J. Hartmanis, L. Hemachandra,

V. Sewelson, K. Wagner, G. Wechsung.

, SIAM Journal on Computing , No. 6, 1988,

pp. 1232–1252

[CKS81] A. K. Chandra, D. C. Kozen, L. J. Stockmeyer. , Journal

of the ACM , 1981, pp. 114–133

[Co71] S. A. Cook. , Proc. 3rd

Annual ACM Symposium on the Theory of Computing (STOC),

1971, pp. 151–158

[Ei76] S. Eilenberg. , Volume B, Aca-

demic Press, New York, 1976

References

61(2)

117

The complexity of promise problems

with applications to public-key crytography

Gap-definable count-

ing classes

Computers and Intractability: A Guide

to the Theory of NP-completeness

Computational complexity of probabilistic Turing machines

General Lattice Theory

Counting Classes with Finite Accep-

tance Types

Threshold computation and

cryptographic security

Feasable Computations and Provable Complexity

Properties

Complexity classes without ma-

chines: on complete languages for UP

On complete problems for NP co-

On the computational complexity of al-

gorithms

[ESY84] S. Even, A. Selman, Y. Yacobi.

, Information and Con-

trol , 1984, pp. 159–173

[FFK94] S. A. Fenner, L. J. Fortnow, S. A. Kurtz.

, Journal of Computer and System Sciences , 1994,

pp. 116–148

[GJ79] M. R. Garey, D. S. Johnson.

, Freeman, San Francisco, 1979

[Gi77] J. Gill. ,

SIAM Journal of Computing , 1977, pp. 675–695

[Gr78] G. Gr¨

atzer. , Birkh¨

auser Verlag, Basel, 1978

[GW87] T. Gundermann, G. Wechsung.

, Computers and Artificial Intelligence No. 5, 1987,

pp. 395–409

[HHT92] Y. Han, L. Hemachandra, T. Thierauf.

, Technical Report No. 443, Department of

Computer Science, University of Rochester, 1992

[Har78] J. Hartmanis.

, CBMS-NSF Regional Conference Series in Applied

Mathematics, Society for Industrial and Applied Mathematics,

Philadelphia, 1978

[HH88] J. Hartmanis, L. A. Hemachandra.

, Theoretical Computer Sci-

ence , 1988, pp. 129–142

[HI85] J. Hartmanis, N. Immerman.

, 12th International Colloquium on Automata, Languages and

Programming (ICALP), Lecture Notes in Computer Science 194,

Springer Verlag, 1985, pp. 250–259

[HS65] J. Hartmanis, R. E. Stearns.

, Transactions of the American Mathematical Society ,

1965, pp. 285–306

References

Almost Optimal Lower Bounds for Small Depth Circuits

Structure of complexity classes: separations,

collapses and completeness

Relations among mod–classes

Locally definable acceptance types for polynomial

time machines

Complexity classes with finite acceptance types

Complexity classes defined via k-valued functions

On the power of polynomial time bit-computations

On balanced vs. unbal-

anced computation trees

[Has86] J. Hastad. ,

Proceedings of the 18th ACM Symposium on Theory of Computing

(STOC), 1986, pp. 6–20

[Hem88] L. A. Hemachandra.

, Proceedings Mathematical Foundations

of Computer Science (MFCS), Lecture Notes in Computer Science

324, Springer Verlag, 1988, pp.59–72

[Her90] U. Hertrampf. , Theoretical Computer

Science , 1990, pp. 325–328

[Her92a] U. Hertrampf.

, Proc. 9th Symposium on Theoretical Aspects of

Computer Science (STACS), Lecture Notes in Computer Science

577, Springer Verlag, 1992, pp. 199–207

[Her94a] U. Hertrampf.

Proc. 11th Symposium on Theoretical Aspects of Computer Science

(STACS), Lecture Notes in Computer Science 775, Springer Verlag,

1994, pp. 543–553

[Her94b] U. Hertrampf. ,

Proc. 9th Structure in Complexity Theory Conference, 1994,

pp. 224–234

[HL*93] U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K. Wag-

ner. , Proc. 8th

Structure in Complexity Theory Conference, 1993, pp. 200–207

[HVW94] U. Hertrampf, H. Vollmer, K. W. Wagner.

, Technical Report No. 82, Institut f¨

ur In-

formatik, Universit¨

at W¨

urzburg, 1994

[Heu89] U. Heuter. Generalized definite tree languages, Proc. Conference on

Mathematical Foundations of Computer Science (MFCS), Lecture

Notes in Computer Science 379, Springer Verlag, 1989, pp. 270–

280

References

Introduction to Automata Theory, Lan-

guages, and Computation

Nondeterministic space is closed under complemen-

tation

Logspace and logtime leaf lan-

guages

A catalog of complexity classes

Reducibility among combinatorial problems

Some connections between nonuniform and

uniform complexity classes

Turing machines that take advice

Representation of events in nerve nets and finite au-

tomata

The Graph Isomorphism Problem:

Its Structural Complexity

Some connections between representability of com-

plexity classes and the power of formal systems of reasoning

[HU79] J. Hopcroft, J. Ullman.

, Addison-Wesley, Reading, MA, 1979

[Im88] N. Immerman.

, SIAM Journal of Computing , 1988, pp. 935–938.

[JMT94] B. Jenner, P. McKenzie, D. Th´

erien.

, Proc. 9th Structure in Complexity Theory Conference, 1994

[Jo90] D. S. Johnson. , in: J. van Leeuwen,

ed., Handbook of Theoretical Computer Science, Volume A, North-

Holland, Amsterdam 1990

[Ka72] R. Karp. ,

in: R. E. Miller and J. W. Thatcher, eds., Complexity of Computer

Computations, Plenum, New York, 1972, pp. 85–103

[KL80] R. M. Karp, R. J. Lipton.

, Proc. 12th Annual ACM Symposium on

Theory of Computing (STOC), 1980, pp. 302–309

[KL82] R. M. Karp, R. J. Lipton. , En-

seignement Math´

ematique , 1982, pp. 191–209

[Kl56] S. C. Kleene.

, Automata Studies, Princeton University Press, Princeton,

1956, pp. 3-42

[KST89] J. K¨

obler, U. Sch¨

oning, J.Tor´

an. On counting and approximation,

Acta Informatica , 1989, pp. 363–379

[KST93] J. K¨

obler, U. Sch¨

oning, J.Tor´

an.

, Birkh¨

auser Verlag, 1993

[Kow84] W. Kowalczyk.

Proc. Conference on Mathematical Foundations of Computer Sci-

ence (MFCS), Lecture Notes in Computer Science 176, Springer

Verlag, 1984, pp. 364-369

References

The complexity of optimization problems

On the structure of polynomial-time reducibilities

Universal sequential search problems

A logical calculus of the ideas immanent

in nervous activity

Extended locally definable accep-

tance types

The complexity of facets (and

some facets of complexity)

Two remarks on the power of

counting

On the complexity of unique solutions

Promise Problems Complete for Complexity Classes

On the theory of the PTIME degrees of the

recursive sets

On relativization and the existence of complete sets

[Kr88] M. W. Krentel. , Journal of

Computer and System Sciences , 1988, pp 490–509

[La75] R. Ladner. , Jour-

nal of the ACM , 1975, pp. 155–171

[Le73] L. Levin. , Problems of Infor-

mation Transmission , 1973, pp. 265-266

[MP43] W. S. McCulloch, W. Pitts.

, Bull. Math. Biophysics , 1943, pp. 115–133

[NR93] R. Niedermeier, P.Rossmanith.

, 10th Symposium on Theoretical Aspects of Computer

Science (STACS), Notes in Computer Science 665, Springer Verlag,

1993, pp. 473–483

[PY82] C. H. Papadimitriou, M. Yannakakis.

, Proc. 14th Annual ACM Symposium on

the Theory of Computing (STOC), 1982, pp. 255–260

[PZ83] C.H. Papadimitriou, S.K. Zachos.

, 6th GI Conference on Theoretical Computer Science,

Lecture Notes in Computer Science 145, Springer Verlag, 1983,

pp. 269–276

[Pa84] C. H. Papadimitriou. , Journal

of the ACM No. 2, 1984, pp. 392–400

[Se88] A. L. Selman. ,

Information and Computation , 1988, pp. 87–98

[ShS90] J. Shinoda, T. A. Slaman.

, Journal of Computer and System Sciences , 1990,

pp. 321–366

[Si82] M. Sipser. , 9th

International Colloquium on Automata, Languages and Program-

ming (ICALP), Lecture Notes in Computer Science 140, Springer

Verlag, 1982, pp. 523–531

References

The polynomial-time Hierarchy

The method of forced enumeration for nondeter-

mistic automata

PP is as hard as the Polynomial Time Hierarchy

Counting classes are at least as hard as the

Polynomial Time Hierarchy

Complexity classes defined by counting quantifiers

The relative complexity of checking and evaluating

The complexity of computing the permanent

Relativizable and nonrelativizable theorems in

the polynomial theory of algorithms

On different reducibility notions for function classes

Komplexit¨atsklassen von Funktionen

Some observations on the connection between count-

ing and recursion

The complexity of combinatorial problems with suc-

cinct input representation

[St77] L. Stockmeyer. , Theoretical Com-

puter Science , 1977, pp. 23–33

[Sz88] R. Szelepcsenyi.

, Acta Informatica , 1988, pp. 279-284

[To91] S. Toda. , SIAM

Journal on Computing , 1991, pp. 865–877

[TO92] S. Toda, M. Ogiwara.

, SIAM Journal of Computing , 1992,

pp. 316–328

[Tor91] J. Toran. , Journal

of the ACM , 1991, pp. 753–774

[Va76] L. G. Valiant. ,

Information Processing Letters , 1976, pp. 20–23

[Va79] L. G. Valiant. , Theoret-

ical Computer Science , 1979, pp. 189–201

[Ve93] N. K. Vereshchagin.

(Russian), Izvestija Rossijskoj

Akademii Nauk No. 2, 1993, pp. 51–90 (an English translation is

available as a manuscript and is to appear in 1994)

[Vo94a] H. Vollmer. ,

Proc. 11th Symposium on Theoretical Aspects of Computer Science

(STACS), Lecture Notes in Computer Science 775, Springer Verlag,

1994, pp. 449–460

[Vo94b] H. Vollmer. , Dissertation

(Ph.D. Thesis), Universit¨

at W¨

urzburg, 1994

[Wa86a] K. W. Wagner.

, Theoretical Computer Science , 1986, pp. 131–

147

[Wa86b] K. W. Wagner.

, Acta Informatica , 1986, pp. 325–356

References

More complicated questions about maxima and min-

ima, and some closures of NP

Bounded query classes

Complete sets and the Polymomial-Time Hierachy

Separating the Polynomial Time Hierarchy by Oracles

Probabilistic Quantifiers and Games

[Wa87] K. W. Wagner.

, Theoretical Computer Science ,

1987, pp. 53–80.

[Wa90] K. W. Wagner. , SIAM Journal of Comput-

ing , No. 5, 1990, pp. 833-846

[Wr77] C. Wrathall. ,

Theoretical Computer Science , 1977, pp. 23–33

[Yao85] A. Yao. ,

Proc. 26th Annual IEEE Symposium on Foundations of Computer

Science (FOCS), 1985, pp. 1-10

[Za88] S. Zachos. , Journal of Com-

puter and System Sciences , 1988, pp. 433-451

Subject Index

Symbol Index

Index of Classes

Lebenslauf

Name Hermann Bernd Borchert

Geburtsdatum geboren am 21. August 1962 in Thuine/Emsland, Niedersachsen

Eltern Bernhard Borchert, Maschinenbau-Ingenieur, und Paula Borchert

Staatsangeh¨

origkeit deutsch

Familienstand ledig

Mai 1982 Abitur am Gymnasium Georgianum Lingen/Ems

Juli 1982 – Sept. 1983 Wehrdienst

Okt. 1982– Dez. 1990 Studium der Mathematik und Informatik

in Hagen, M¨

unster, M¨

unchen, Boston und Heidelberg

Oktober 1984 Vordiplom in Mathematik

Mai 1988 Master of Arts in Computer Science, Boston University

Dezember 1988 Diplom in Informatik, FernUniversit¨

at Hagen

Dezember 1990 Diplom in Mathematik, Universit¨

at Heidelberg

Mai 1989 – Sept. 1991 Freier Mitarbeiter bei IBM Heidelberg

Okt. 1991– Sept. 1992 LGFG Stipendium des Landes Baden-W¨

urttemberg

Jan. 1992 – Juni 1992 Aufenthalt an der Cornell University, Ithaca, New York

seit Okt. 1992 Assistent am Lehrstuhl f¨

ur Logik am Mathematischen Institut

der Universit¨

at Heidelberg