Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 7: Complexity Hierachies

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes I
First, we ask how the number of tapes does influence thecomplexity of Turing machine computations. As we shall see,the answer depends on both the complexity measureconsidered and the type of the TM (deterministic or
nondeterministic).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes I
First, we ask how the number of tapes does influence thecomplexity of Turing machine computations. As we shall see,the answer depends on both the complexity measureconsidered and the type of the TM (deterministic or
nondeterministic).
Theorem 1 (Hartmanis and Stearns (1965))
Let f : N → R>0 be any bounding function. Then we have
TIME(f(n)) = Time2 ((f(n))2 ) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes II
Proof. Let M be any deterministic k-tape TM, k > 1, such that
TM (n) 6 f(n) for all n ∈ N. For showing the theorem, it
suffices to construct a deterministic 2-tape TM M 0 satisfying
L(M 0 ) = L(M) and TM 0 (n) 6 c(TM (n))2 for some constantc > 0. This is done as follows:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes II
Proof. Let M be any deterministic k-tape TM, k > 1, such that
TM (n) 6 f(n) for all n ∈ N. For showing the theorem, it
suffices to construct a deterministic 2-tape TM M 0 satisfying
L(M 0 ) = L(M) and TM 0 (n) 6 c(TM (n))2 for some constantc > 0. This is done as follows:
Let Y be the alphabet used by M on all its k − 1 work tapes andassume without loss of generality that # < Y. Then M 0 will use
the alphabet (Y × {0, 1})k−1 ∪ {#} on its work tape. The ith
component of the form Y × {0, 1} at position z contains thecontent of the ith work tape of M at position z, where “1” isused to mark the actual position of the read-write head of M on
this tape. The symbol # is used to mark the left and right end ofwhat was written on the work tape of M 0 .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes III
−1 0
*

1

2

3

input tape* a

−1 0 1 2 3
b0 b1 b2 b3 . .

−1 0 1 2 3c0 c1 c2 c3 c4 c5.

1st work tape(k − 1)th work tapeFigure 1: Illustration for the use of the new letters

What is inside the red box is becoming the new letter((b1 , 0), . . . , (c1 , 0)) which is then written in the cell between -1
and 0 of the single work tape of M 0 .
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes IV
The simulation of one step of computation performed by M isdone by M 0 as follows: Let w be the input to both M and M 0 .
On the input tape, both machines behave identically. On its
work tape M 0 behaves as follows:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes IV
The simulation of one step of computation performed by M isdone by M 0 as follows: Let w be the input to both M and M 0 .
On the input tape, both machines behave identically. On its
work tape M 0 behaves as follows:(1) The read-write head on the work tape of M 0 is reading thewhole inscription between the two end markers # from left
to right. While doing this, M 0 memorizes in states the k − 1tape contents marked with 1, i.e., the actual head positions
on the k − 1 work tapes of M.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes IV
The simulation of one step of computation performed by M isdone by M 0 as follows: Let w be the input to both M and M 0 .
On the input tape, both machines behave identically. On its
work tape M 0 behaves as follows:(1) The read-write head on the work tape of M 0 is reading thewhole inscription between the two end markers # from left
to right. While doing this, M 0 memorizes in states the k − 1tape contents marked with 1, i.e., the actual head positions
on the k − 1 work tapes of M.
(2) By using the Turing table of M, the machine M 0 iscomputing the changes to be made, andComplexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes IV
The simulation of one step of computation performed by M isdone by M 0 as follows: Let w be the input to both M and M 0 .
On the input tape, both machines behave identically. On its
work tape M 0 behaves as follows:(1) The read-write head on the work tape of M 0 is reading thewhole inscription between the two end markers # from left
to right. While doing this, M 0 memorizes in states the k − 1tape contents marked with 1, i.e., the actual head positions
on the k − 1 work tapes of M.
(2) By using the Turing table of M, the machine M 0 iscomputing the changes to be made, and(3) then actually performing these changes by moving its
read-write head on the work tape from right to left. By
doing this, it possibly has also to move its end markers #.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes V

Consequently, the length of the tape inscription on the work
tape of M 0 cannot exceed 2 · TM (w) + 2. Hence, one step of M’s
computation can be simulated in O(TM (w)) steps by M 0 . At all,TM (w) many steps of M’s computation haveto be simulated.

Thus, M 0 performs at most O (TM (w))2 many steps. By
Theorem 6.3 the assertion of the theorem follows.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes V

Consequently, the length of the tape inscription on the work
tape of M 0 cannot exceed 2 · TM (w) + 2. Hence, one step of M’s
computation can be simulated in O(TM (w)) steps by M 0 . At all,TM (w) many steps of M’s computation haveto be simulated.

Thus, M 0 performs at most O (TM (w))2 many steps. By
Theorem 6.3 the assertion of the theorem follows.
Note that the same construction also works if we wish tosimulate a deterministic k-tape TM by a deterministic one-tape
TM. Thus, we even have the following result.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes VI
Corollary 1
Let a f : N → R>0 be any bounding function. Then we have
TIME(f(n)) = Time((f(n))2 ) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Reducing the Number of Tapes VI
Corollary 1
Let a f : N → R>0 be any bounding function. Then we have
TIME(f(n)) = Time((f(n))2 ) .
Furthermore, the proof of the latter theorem directly allows forthe following corollary:
Corollary 2
Let a f : N → R>0 be any bounding function. Then we have
SPACE(f(n)) = Space2 (f(n)) .
Proof. The proof is identical to the proof of Theorem 1, since thesimulation given there is not increasing the amount of spaceneeded, i.e., SM 0 (w) 6 SM (w).
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages I
Consequently, when studying the amount of space needed toaccept non-regular languages, it suffices to deal with 2-tapeTuring machines. Recalling a bit automata theory, we directly
get the following lemma:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages I
Consequently, when studying the amount of space needed toaccept non-regular languages, it suffices to deal with 2-tapeTuring machines. Recalling a bit automata theory, we directly
get the following lemma:
Lemma 1For every regular language L there is a deterministic 2-tape TM M
such that L = L(M) and SM (n) = 1 for all n ∈ N.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages I
Consequently, when studying the amount of space needed toaccept non-regular languages, it suffices to deal with 2-tapeTuring machines. Recalling a bit automata theory, we directly
get the following lemma:
Lemma 1For every regular language L there is a deterministic 2-tape TM M
such that L = L(M) and SM (n) = 1 for all n ∈ N.
Question
How much space is needed for accepting non-regular
languages?

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages II
Answering this question reveals a further surprise.
We also need the following definition:
Definition 1
Let M be a TM. A macro state of M is a tuple containing thefollowing:(1) the head position on the input tape of M,(2) the actual state of M,(3) for every work tape of M the inscription of all cells visited
so far and the actual position of the read-write head.
If (1) is omitted, then we refer to the resulting tuple asconfiguration of M.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages III
Note that the definition of configuration, when applied to
one-tape TMs means that we just record the actual state of
the TM.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages III
Note that the definition of configuration, when applied to
one-tape TMs means that we just record the actual state of
the TM.
First, we show that enlarging the space available to any
constant does not allow to accept non-regular languages.
Theorem 2
Let c > 0 be any constant and let M be a deterministic 2-tape TM
such that SM (n) 6 c for all n ∈ N. Then L(M) ∈ REG.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages III
Note that the definition of configuration, when applied to
one-tape TMs means that we just record the actual state of
the TM.
First, we show that enlarging the space available to any
constant does not allow to accept non-regular languages.
Theorem 2
Let c > 0 be any constant and let M be a deterministic 2-tape TM
such that SM (n) 6 c for all n ∈ N. Then L(M) ∈ REG.
Proof. We show that there is a constant ĉ such that M can workat most ĉn many steps on inputs of length n without reaching acycle.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages IV
Obviously, there are at mostcX
k=0

|B|k =|B|c+1 − 1=: S|B| − 1many pairwise different strings s with |s| 6 c which can be
written on M’s work tape. To write a string of length k on its
work tape, M needs k steps. So M needs at most c · S many
steps to write all these strings on its work tape. To estimate ĉ, itsuffices to assume that M can write all these strings in every of
its states on its work tape. Hence, there are at most c · |Z| · S
many pairwise different steps that can be performed by M on
every input symbol read on its inputs tape. Settingĉ = c · |Z| · S(1)yields that M can work at most ĉn many steps without
reaching a cycle.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages V

cNext, we argue that there is a deterministic one-tape TM M
csuch that TM
c (n) 6 ĉn for all n ∈ N and L(M) = L(M).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages V

cNext, we argue that there is a deterministic one-tape TM M
csuch that TM
c (n) 6 ĉn for all n ∈ N and L(M) = L(M).
c is obtained by encoding all possible inscriptions on
The TM M
M’s work tape into states and the changes M can make on these
inscriptions into state transitions. Here it is crucial that there
are only S many possible inscriptions. Finally, by Theorem 6.2,
we directly get L(M) ∈ REG.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages V

cNext, we argue that there is a deterministic one-tape TM M
csuch that TM
c (n) 6 ĉn for all n ∈ N and L(M) = L(M).
c is obtained by encoding all possible inscriptions on
The TM M
M’s work tape into states and the changes M can make on these
inscriptions into state transitions. Here it is crucial that there
are only S many possible inscriptions. Finally, by Theorem 6.2,
we directly get L(M) ∈ REG.
To make further progress, we extend the definition of traces
made for one-tape TMs by using configurations.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages VI
Definition 2
Let k ∈ N, k > 1, let M be a k-tape TM and w ∈ Σ∗ . We define
the trace of M on input w at position j to be TRM (w, j), where
TRM (w, j) =df the string formed of configurations of M
such that the ith position of TRM (w, j)
is M’s configuration when its head on the
input tape crosses the border j for the ith time .
Furthermore, TRM (w) and TRM (n) are defined as before; i.e.,
for every input string w ∈ Σ∗ and all n ∈ N we set
TRM (w) =df max{|TRM (w, j)| | j ∈ Z}
TRM (n) =df max{TRM (w) | |w| = n} .
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages VII

Note that for k = 1 we just obtain the definition of traces
previously made for deterministic one-tape TMs.
Exercise 1. Prove the following generalization of Lemma 6.1:
Let M be a deterministic TM. If TRM (uvw, |uv|) = TRM (uvw, |u|)then, for all i, j ∈ N, TRM (uvi vj w, |uvi |) = TRM (uw, |u|) anduvi vj w ∈ L(M) iff uw ∈ L(M).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages VII

Note that for k = 1 we just obtain the definition of traces
previously made for deterministic one-tape TMs.
Exercise 1. Prove the following generalization of Lemma 6.1:
Let M be a deterministic TM. If TRM (uvw, |uv|) = TRM (uvw, |u|)then, for all i, j ∈ N, TRM (uvi vj w, |uvi |) = TRM (uw, |u|) anduvi vj w ∈ L(M) iff uw ∈ L(M).
Next, we show a complexity gap for the complexity measure“space complexity” with respect to the acceptability of
non-regular languages.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages VIII
Theorem 3 (Stearns, Hartmanis, and Lewis II (1965))
Let M be any deterministic 2-tape TM such thatSM (n) = o(log log n). Then L(M) is regular.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages VIII
Theorem 3 (Stearns, Hartmanis, and Lewis II (1965))
Let M be any deterministic 2-tape TM such thatSM (n) = o(log log n). Then L(M) is regular.
By Theorem 2 it suffices to show that there is a constant c > 0such that SM (n) < c. We continue indirectly.
Suppose there is an infinite sequence (vi )i∈N of strings suchthat
SM (vi+1 ) > SM (vi )for all i ∈ N .

(2)

We can choose the strings vi in a way such that for all i ∈ N
SM (u) < SM (vi )Complexity and Cryptography

for all strings u with |u| < |vi | .
c Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages IX

Among all traces TRM (vi , j), where 0 < j < |vi |, there are notwo equal traces.
Suppose there are positions j1 and j2 with 0 < j1 < j2 < |vi | andTRM (vi , j1 ) = TRM (vi , j2 ). Then all symbols between j1 and j2
in vi can be erased without reducing the space needed, acontradiction to (2).
By Exercise 1, without loss of generality, we can assume thateach single trace does not contain two identical configurations,since the part of M’s work done between such identicalconfigurations cannot influence the acceptance of the input
string given.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages X
Provided M = [B, Z, A] uses ` cells on its work tape, there are at
most|B|`+1 − 1c` = |Z| ··`|B| − 1(3)

many possible configurations of length at most `. By Exercise 1,
we conclude that there are at most cc` ` many different traces
that can be built from the possible configurations. Since there
are no two identical traces among all traces TRM (vi , j), where
0 < j < |vi |, we therefore have|vi | 6 cc` ` ,where` = SM (vi ) .

(4)`

Using (3) and (4), we see that there is an r such that |vi | 6 rr .
Hence, log log |vi | 6 c · ` = c · SM (vi ) for some constant c.
Therefore, 1 6 c · SM (vi )/ log log |vi |, a contradiction toSM (n) = o(log log n).
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages XIThis contradiction is due to (2), and so (2) cannot hold. Hence,
SM (n) 6 c for a constant c > 0. By Theorem 2, we therefore
have L(M) ∈ REG.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages XIThis contradiction is due to (2), and so (2) cannot hold. Hence,
SM (n) 6 c for a constant c > 0. By Theorem 2, we therefore
have L(M) ∈ REG.
The gap established in Theorem 3 cannot be improved. Let
Lbin = {1 ∗ 10 ∗ 11 ∗ · · · ∗ bin(k) | k ∈ N+ } ,where bin(k) denotes the binary representation of the number k.
Clearly, Lbin < REG (Nerode’s theorem).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages XIThis contradiction is due to (2), and so (2) cannot hold. Hence,
SM (n) 6 c for a constant c > 0. By Theorem 2, we therefore
have L(M) ∈ REG.
The gap established in Theorem 3 cannot be improved. Let
Lbin = {1 ∗ 10 ∗ 11 ∗ · · · ∗ bin(k) | k ∈ N+ } ,where bin(k) denotes the binary representation of the number k.
Clearly, Lbin < REG (Nerode’s theorem).
But we have the following lemma:
Lemma 2
There exists a deterministic TM M such that SM (n) = log log n
and L(M) = Lbin .
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages XII

Applying the techniques developed so far, we can prove thefollowing:
Theorem 4
Let M be any deterministic TM accepting the language
L(M) = {0n 1n | n ∈ N}. Then we have SM (n) , o(log n).
Proof. The proof is left as an exercise.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Regular Languages XII

Applying the techniques developed so far, we can prove thefollowing:
Theorem 4
Let M be any deterministic TM accepting the language
L(M) = {0n 1n | n ∈ N}. Then we have SM (n) , o(log n).
Proof. The proof is left as an exercise.
Next, we turn our attention to complexity hierarchies fordeterministic Turing machines.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies I
Before dealing with complexity hierarchies, it is meaningful to
ask whether or not we can improve Theorem 1. This is indeed
the case as the following theorem shows:Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies I
Before dealing with complexity hierarchies, it is meaningful to
ask whether or not we can improve Theorem 1. This is indeed
the case as the following theorem shows:
Theorem 5 (Hennie and Stearns (1966))
Let f : N → N be any bounding function. Then we have
TIME(f(n)) = Time3 (f(n) · log f(n)) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies I
Before dealing with complexity hierarchies, it is meaningful to
ask whether or not we can improve Theorem 1. This is indeed
the case as the following theorem shows:
Theorem 5 (Hennie and Stearns (1966))
Let f : N → N be any bounding function. Then we have
TIME(f(n)) = Time3 (f(n) · log f(n)) .

We omit the proof of Theorem 5 here, since there are several
more important theorems we want to deal with in this course.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies II
Theorem 6
Assuming an appropriate enumeration of all deterministic TMs thefollowing holds:(1) There is a universal deterministic TM U for all deterministic
TMs (Mi )i∈N such that
L(U) = {bin(i) ∗ w | w ∈ L(Mi ), i ∈ N} ,and for every i ∈ N there is a constant ci such that for all w ∈ Σ∗ thecondition TU (|bin(i) ∗ w|) < ci · TMi (|w|) · log TMi (|w|) is fulfilled.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies II
Theorem 6
Assuming an appropriate enumeration of all deterministic TMs thefollowing holds:(1) There is a universal deterministic TM U for all deterministic
TMs (Mi )i∈N such that
L(U) = {bin(i) ∗ w | w ∈ L(Mi ), i ∈ N} ,and for every i ∈ N there is a constant ci such that for all w ∈ Σ∗ thecondition TU (|bin(i) ∗ w|) < ci · TMi (|w|) · log TMi (|w|) is fulfilled.
(2) There is a universal deterministic TM U for all deterministic TMs(Mi )i∈N such that
L(U) = {bin(i) ∗ w | w ∈ L(Mi ), i ∈ N} ,and for every i ∈ N there is a constant ci such that for all w ∈ Σ∗ thecondition SU (|bin(i) ∗ w|) < ci · SMi (|w|) is fulfilled.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies III
Proof. We showed the existence of universal TMs in our course
Theory of Computation. For showing the theorem, theenumeration is chosen in a way such that the code of Mi at theuniversal machine is just bin(i). Moreover, the universal
deterministic TM U possesses an input tape and at least twowork tapes. Any fixed number k > 2 of work tapes will do.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies III
Proof. We showed the existence of universal TMs in our course
Theory of Computation. For showing the theorem, theenumeration is chosen in a way such that the code of Mi at theuniversal machine is just bin(i). Moreover, the universal
deterministic TM U possesses an input tape and at least twowork tapes. Any fixed number k > 2 of work tapes will do.
On input bin(i) ∗ w, the universal TM U simulates thedeterministic TM Mi on input w step by step. Assuming thecoding is appropriately chosen, for doing this, it suffices that U
reads in each simulation step the “programming code” bin(i),memorizes the actions to be performed and performs the step
to be simulated.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies IV
Hence, the constant ci is obtained by counting the number ofsteps the universal machine needs for simulating one stepof Mi . Furthermore, the simulation has to incorporate thereduction of work tapes to the previously fixed number k. By
Theorem 5, this reduction requires that in the deterministic caseTMi (w) · log (TMi (w)) steps have to be simulated. Thus, Part (1)of the theorem follows.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies IV
Hence, the constant ci is obtained by counting the number ofsteps the universal machine needs for simulating one stepof Mi . Furthermore, the simulation has to incorporate thereduction of work tapes to the previously fixed number k. By
Theorem 5, this reduction requires that in the deterministic caseTMi (w) · log (TMi (w)) steps have to be simulated. Thus, Part (1)of the theorem follows.
For showing Part (2), the only difference is the application ofCorollary 2 for the tape reduction in the deterministic case.
Note that this corollary also causes the improvement in Part (2)concerning the space complexity needed by the universal
deterministic TM U.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies V
Theorem 7 (Hennie and Stearns (1966))
Let f, g : N → N be any bounding functions such that g is
T -constructible and f(n) log f(n) = o(g(n)). Then we have
TIME(f(n)) ⊂ TIME(g(n)) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies V
Theorem 7 (Hennie and Stearns (1966))
Let f, g : N → N be any bounding functions such that g is
T -constructible and f(n) log f(n) = o(g(n)). Then we have
TIME(f(n)) ⊂ TIME(g(n)) .
Proof. Since the assumption implies f(n) < f(n) log f(n) < g(n)for all but finitely many n, the inclusion
TIME(f(n)) ⊆ TIME(g(n)) is obvious.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies V
Theorem 7 (Hennie and Stearns (1966))
Let f, g : N → N be any bounding functions such that g is
T -constructible and f(n) log f(n) = o(g(n)). Then we have
TIME(f(n)) ⊂ TIME(g(n)) .
Proof. Since the assumption implies f(n) < f(n) log f(n) < g(n)for all but finitely many n, the inclusion
TIME(f(n)) ⊆ TIME(g(n)) is obvious.
We have to show that there is a language
Ld ∈ TIME(g(n)) \ TIME(f(n)). This is done by diagonalization.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VI

We construct the wanted language Ld by using the universal
TM U from Theorem 6 and by defining a deterministic TM M
as follows: Then, Ld contains all strings w, w = 0k bin(i) thatare accepted by M and nothing else.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VI

We construct the wanted language Ld by using the universal
TM U from Theorem 6 and by defining a deterministic TM M
as follows: Then, Ld contains all strings w, w = 0k bin(i) thatare accepted by M and nothing else.
On input w, w = 0k bin(i), the machine M works as U on input
bin(i) ∗ w. Moreover, M uses a clock for g(n) and rejects its
input if U does not stop within g(|w|) many steps. If U doesstop within g(|w|) many steps, then M rejects the input if U
accepts and accepts if U rejects.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VI

We construct the wanted language Ld by using the universal
TM U from Theorem 6 and by defining a deterministic TM M
as follows: Then, Ld contains all strings w, w = 0k bin(i) thatare accepted by M and nothing else.
On input w, w = 0k bin(i), the machine M works as U on input
bin(i) ∗ w. Moreover, M uses a clock for g(n) and rejects its
input if U does not stop within g(|w|) many steps. If U doesstop within g(|w|) many steps, then M rejects the input if U
accepts and accepts if U rejects.
Thus, by construction we already know Ld ∈ TIME(g(n)).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VII
Suppose there is a deterministic TM Mi such that
Ld = L(Mi )andTMi (n) 6 f(n) .

(5)

By Theorem 6, we may conclude that for input 0k bin(i) the
following holds:
TU (|bin(i) ∗ 0k bin(i)|) 6 ci · TMi (|0k bin(i)|) log TMi (|0k bin(i)|)

6 ci · f(|0k bin(i)|) log f(|0k bin(i)|) .

Moreover, if k is sufficiently large, we also have
TU (|bin(i) ∗ 0k bin(i)|) 6 g(|0k bin(i)|) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VIII
Hence, Theorem 6 and the construction of M imply that0k bin(i) ∈ L(Mi )iff

0k bin(i) ∈ L(M) (∗ since L(Mi ) = Ld = L(M) ∗)iffbin(i) ∗ 0k bin(i) < L(U)iffk(∗ by construction of M ∗)0 bin(i) < L(Mi ) (∗ by definition of L(U) ∗) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies VIII
Hence, Theorem 6 and the construction of M imply that0k bin(i) ∈ L(Mi )iff

0k bin(i) ∈ L(M) (∗ since L(Mi ) = Ld = L(M) ∗)iffbin(i) ∗ 0k bin(i) < L(U)iffk(∗ by construction of M ∗)0 bin(i) < L(Mi ) (∗ by definition of L(U) ∗) .

Thus, we have obtained the contradiction 0k bin(i) ∈ L(Mi ) iff
0k bin(i) < L(Mi ). This contradiction is caused by our
Supposition (5). Consequently, our supposition is false. Since
there is obviously a deterministic TM Mi with Ld = L(Mi ), wemust conclude that every TM Mi with Ld = L(Mi ) has tosatisfy TMi (n) > f(n). So we arrive at Ld < TIME(f(n)).
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies IX
Applying the same ideas as in the proof of Theorem 7 wedirectly get the following hierarchy theorem for deterministic
space complexity:
Theorem 8
Let g be any S-constructible function and let f(n) be any space boundsuch that f(n) = o(g(n)). Then we have
SPACE(f(n)) ⊂ SPACE(g(n)) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies IX
Applying the same ideas as in the proof of Theorem 7 wedirectly get the following hierarchy theorem for deterministic
space complexity:
Theorem 8
Let g be any S-constructible function and let f(n) be any space boundsuch that f(n) = o(g(n)). Then we have
SPACE(f(n)) ⊂ SPACE(g(n)) .
The hierarchy theorems already proved do yield only infinite
deterministic complexity time and space hierarchies provided
there are arbitrarily complex T -constructible and S-constructible
functions. Therefore, we should prove the following exercise:Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Deterministic Complexity Hierarchies X

Exercise 2. For every general recursive function f : N → N there
exist general recursive functions g, g 0 : N → N such that(1) f(n) < g(n) and f(n) < g 0 (n) for all n ∈ N, and(2) g is T -constructible, and g 0 is S-constructible.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines I

Definition 3
A TM M = [B, Z, A] is called nondeterministic k-tape TM, k > 1,
provided B ∪ Z = ∅, and(1) B = {∗, | , . . .} is a finite set such that |B| > 2,
(2) Z = {zs , zf , . . .} is a finite set such that |Z| > 2,
(3) A : Z \ {zf } × Bk → ℘ (B × {L, N, R})k × Z \ {∅}and M has an input-tape with read-only head (read-write headiff k = 1) and k − 1 work-tapes (none iff k = 1 ) each of which
possesses exactly one read-write head.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines II

Again, in every step M moves k heads and observes k cells(one on each tape). Also, we make the restriction that M is notallowed to write on its input-tape iff k > 1.
Initially, M is in state zs (the start state) and all heads areobserving the first cell located right to position 0. What M is
writing into the cells it is observing and which move the heads
make is decided nondeterministically by choosing one
possibility from the set of allowed possibilities(cf. Condition (3)).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines III

Looking at Definition 6.4 and Definition 3, we see that the maindifference to a deterministic TM is Condition (3). For adeterministic TM we had
A ⊆ Z \ {zf } × Bk × (B × {L, N, R})k × Z ,while now we haveA:

Z \ {zf } × Bk → ℘ (B × {L, N, R})k × Z \ {∅} .

That is, a nondeterministic TM possesses in each step a set of
possible continuations. From this set, one possibility is chosen
nondeterministically.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines IV

Initially, M is in state zs (the start state) and all heads areobserving the first cell located right to position 0. But now, on
one and the same input there are many possible computations
that can be performed by M. Thus, we also have to modify thedefinition of accepting a language. As before, we assume Σ ⊆ B
to be the input alphabet, where in particular ∗ < Σ.
This is done as follows:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines V
Definition 4
A language L ⊆ Σ∗ is accepted by a nondeterministic k-tape
TM M if for every string w ∈ Σ∗ the following conditions are
satisfied:
If w is written on the empty input-tape of M (beginning incell 0) and M is started such that the read-only head on the
input-tape is put on the leftmost symbol of w and all otherheads are put on the first cell located right to position 0 instate zs then, if w ∈ L, there is a possible computation path suchthat M stops after having executed finitely many steps instate zf and the cell observed by M on its first work-tape instate zf contains a | . In this case we also write M(w) = | .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines VI

In the following, we use NTM as an abbreviation for
nondeterministic TMs.
In contrast to a deterministic TM, if w < L then an NTM M is
not supposed to deliver any information. We do not evenrequire M to stop on inputs w < L. By L(M) we denote thelanguage accepted by M.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines VI

In the following, we use NTM as an abbreviation for
nondeterministic TMs.
In contrast to a deterministic TM, if w < L then an NTM M is
not supposed to deliver any information. We do not evenrequire M to stop on inputs w < L. By L(M) we denote thelanguage accepted by M.
Next, we define time and space complexity for NTMs.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines VII
Definition 5
Let M be an NTM and w ∈ Σ∗ . We define TM (w) to be the minimum
number of steps executed by M on input w among all its accepting
computations if w ∈ L(M), and the minimum number of steps executedby M among all its computation executed on input w if w < L(M).
We define SM (w) to be the minimum number of all cells on M’s work
tapes visited by the read-write heads of M on input w among all its
accepting computations if w ∈ L(M) and minimum number of all cells
on M’s work tapes visited by the read-write heads of M on input w
among all its computations if w < L(M). Both functions T and S
remain undefined if there is no computation of M on input w thatstops. Furthermore, we set

Complexity and Cryptography

TM (n)=df

max{TM (w) | |w| = n} ,SM (n)=dfmax{SM (w) | |w| = n} .

c Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Nondeterministic Turing Machines VIII
Finally, we define the resulting complexity classes as follows:
NTimek (f(n)) =df {L(M) | M is a nondeterministic k-tape TM
and TM (n) 6 f(n) for all n ∈ N} ;NSpacek (f(n)) =df {L(M) | M is a nondeterministic k-tape TM
and SM (n) 6 f(n) for all n ∈ N} ;NTIME(f(n)) =df {L(M) | M is an NTM andTM (n) 6 f(n) for all n ∈ N} ;NSPACE(f(n)) =df {L(M) | M is an NTM andSM (n) 6 f(n) for all n ∈ N} .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Richard Edwin Stearns

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Regular Languages

Hierarchies

NDTM

End

Juris Hartmanis

Complexity and Cryptographyc Thomas Zeugmann