Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

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

Lecture 8: More about Complexity Classes

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions I
We ask whether or not we can improve our results obtained so
far for NTMs.
Surprisingly, allowing two work tapes for NTMs is alreadysufficient to simulate any NTM without increasing the timecomplexity, i.e., we can show the following:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions I
We ask whether or not we can improve our results obtained so
far for NTMs.
Surprisingly, allowing two work tapes for NTMs is alreadysufficient to simulate any NTM without increasing the timecomplexity, i.e., we can show the following:
Theorem 1 (Book, Greibach, Wegbreit (1970))
Let f : N → N be any bounding function. Then we have
NTIME(f(n)) = NTime3 (f(n)) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions II

Proof. Let any nondeterministic k-tape TM M = [B, Z, A] be
given such that k > 3. If k 6 3, the theorem is obvious. Now,
we construct a nondeterministic 3-tape TM M∗ withL(M∗ ) = L(M) and TM∗ (w) = O(TM (w)) for all w.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions II

Proof. Let any nondeterministic k-tape TM M = [B, Z, A] be
given such that k > 3. If k 6 3, the theorem is obvious. Now,
we construct a nondeterministic 3-tape TM M∗ withL(M∗ ) = L(M) and TM∗ (w) = O(TM (w)) for all w.
On its first work tape M∗ is using the tape alphabet B and on its
second work tape the tape alphabet Z × Bk .
On input w, the machine M∗ works as follows:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions III(1) M∗ writes nondeterministically an arbitrary finite numberof symbols on its second work tape. Note that thesesymbols are from Z × Bk , i.e., (k + 1)-tuples.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions III(1) M∗ writes nondeterministically an arbitrary finite numberof symbols on its second work tape. Note that thesesymbols are from Z × Bk , i.e., (k + 1)-tuples.
(2) The ith symbol (zi , b1 , . . . , bk ) written on the second work
tape is interpreted as the actual situation machine M is in
its ith step, i.e., it is assumed to be in state zi and observing
b1 , . . . , bk on its input tape and its k − 1 work tapes.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions III(1) M∗ writes nondeterministically an arbitrary finite numberof symbols on its second work tape. Note that thesesymbols are from Z × Bk , i.e., (k + 1)-tuples.
(2) The ith symbol (zi , b1 , . . . , bk ) written on the second work
tape is interpreted as the actual situation machine M is in
its ith step, i.e., it is assumed to be in state zi and observing
b1 , . . . , bk on its input tape and its k − 1 work tapes.
(3) Using the Turing table of M, the machine M∗ checks
deterministically whether or not the sequence of symbols
on its second work tape is an accepting computation of M
on input w. If it is, M∗ accepts the input w, otherwise theinput w is rejected.
The check is done in k − 1 stages. In stage i, 1 6 i 6 k − 1,
the ith work tape of M is completely documented on thefirst work tape of M∗ .
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions IV

Hence, M∗ can find an accepting computation path in timek · TM (w) = O(TM (w)) if and only if w ∈ L(M).
Finally, the theorem follows by our constant factor speed-up
Theorem from Lecture 6 (see Theorem 6.3).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions V
Dealing with nondeterministic space complexity does not
require any new idea. Looking at the proof of Theorem 7.1, we
immediately realize that the construction performed there canalso be applied in the nondeterministic case. Since this tape
reduction does not increase the amount of space needed, we get
the following corollary:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions V
Dealing with nondeterministic space complexity does not
require any new idea. Looking at the proof of Theorem 7.1, we
immediately realize that the construction performed there canalso be applied in the nondeterministic case. Since this tape
reduction does not increase the amount of space needed, we get
the following corollary:
Corollary 1
Let f : N → N be any bounding function. Then we have
NSPACE(f(n)) = NSpace2 (f(n)) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

More about Tape Reductions VI
Theorem 2
Assuming an appropriate enumeration of all NTMs the following holds:(1) There is a universal NTM V for all NTMs (Mi )i∈N such that
L(V) = {bin(i) ∗ w | w ∈ L(Mi ), i ∈ N} ,and for every i ∈ N there is a constant ci such that for all w ∈ Σ∗ thecondition TV (|bin(i) ∗ w|) < ci · TMi (|w|) is fulfilled.
(2) There is a universal NTM V for all NTMs (Mi )i∈N such that
L(V) = {bin(i) ∗ w | w ∈ L(Mi ), i ∈ N} ,and for every i ∈ N there is a constant ci such that for all w ∈ Σ∗ thecondition SV (|bin(i) ∗ w|) < ci · SMi (|w|) is fulfilled.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Remarks I

The proof methods developed so far are not directly applicableto the nondeterministic case. Looking at the proofs ofTheorems 7 and 8 in Lecture 7, we see that we have taken
advantage of the fact that deterministic complexity classes areclosed under complement.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Remarks I

The proof methods developed so far are not directly applicableto the nondeterministic case. Looking at the proofs ofTheorems 7 and 8 in Lecture 7, we see that we have taken
advantage of the fact that deterministic complexity classes areclosed under complement.
More precisely, if C is a complexity class, then we set
co-C =df {L | L ⊆ Σ∗ , Σ∗ \ L ∈ C} .
We say that a complexity class is closed under complement
if co-C ⊆ C.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Remarks II
While it was fairly easy to complement deterministic
complexity classes by just returning ‘no’ for all accepting
computations, and ‘yes’ to all rejecting computations, thismethod does not work for nondeterministic complexity classes.
The fact that a particular computation did not succeed, is no
guarantee that others do not, so the strategy above could put
some strings both in the language and in its complement.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Remarks II
While it was fairly easy to complement deterministic
complexity classes by just returning ‘no’ for all accepting
computations, and ‘yes’ to all rejecting computations, thismethod does not work for nondeterministic complexity classes.
The fact that a particular computation did not succeed, is no
guarantee that others do not, so the strategy above could put
some strings both in the language and in its complement.
Thus, additional work is needed here. For space complexity
there is the famous Immerman–Szelepcsényi Theorem statingthat NSPACE(f(n)) = co-NSPACE(f(n)) for all S-constructible
bounding functions f satisfying f(n) > log n for all n ∈ N(cf. Theorem 4).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Remarks III
But for nondeterministic time complexity classes no suchtheorem is known. The best one has is the almost trivial result
given by the following exercise:
Exercise 1. Let f : N → N be any T -constructible bounding
function. Then we have




[
[
co-NTIME(f(n)) ⊆TIME 2cf(n) ⊆NTIME 2cf(n) .
c>0

c>0

Nevertheless, we can show a hierarchy theorem for
nondeterministic time complexity classes.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

A Complexity Hierarchy for Nonderterministic Time I
We continue with the following lemma that will help us tocircumvent the problem whether or not nondeterministic timecomplexity classes are closed under complement:
Lemma 1 (Seiferas, Fischer, Meyer (1978))For every NTM Mi there is a constant ci and an NTM Mk such that
L(Mk ) = {w | w ∈ Σ∗ , bin(k) ∗ w ∈ L(Mi )}TMk (w) 6 ci · TMi (bin(k) ∗ w)

andfor all w ∈ Σ∗ .

For a proof, the reader is referred to the book.
Note that the lemma above may be regarded as a variant of the
fixed point theorem.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Complexity Hierarchy for Nonderterministic Time II

Using the latter lemma, we can prove the following hierarchy
theorem for nondeterministic time complexity classes. Before
presenting it, we also need to prove that there are arbitrarily
complex languages acceptable by NTMs. This is done via thefollowing exercise:
Exercise 2. Let g be any T -constructible bounding function and let
M = [B, Z, A] be any NTM such that TM (w) 6 g(|w|). Then there
is a deterministic TM M 0 such that L(M) = L(M 0 ) andTM 0 (w) 6 g(|w|) · kg(|w|) , where k = 2 · |B|.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Complexity Hierarchy for Nonderterministic Time III
Having the result of Exercise 2 on hand, the determinisitic
Hierarchy Theorem directly implies via Exercise 19 that there
are arbitrarily complex languages for nondeterministic timeand nondeterministic space.
Theorem 3 (Seiferas, Fischer, Meyer (1978))Let g : N → N be any T -constructible bounding function and let
f : N → N be any bounding function such that f(n) = o(g(n)) andf(n + 1) = O(g(n)). Then we have
NTIME(f(n)) ⊂ NTIME(g(n)) .
For a proof, the reader is referred to the book.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem I
We are going to prove a nondeterministic space hierarchy
theorem. Fortunately enough, after three decades of failure, in1988 it could be proved that nondeterministic space is closed
under complement. Even more interestingly, in 1988 two proofs
have been published independently of one another by
Immerman and Szelepcsényi, respectively. So, we continue
with the Immerman–Szelepcsényi Theorem.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem I
We are going to prove a nondeterministic space hierarchy
theorem. Fortunately enough, after three decades of failure, in1988 it could be proved that nondeterministic space is closed
under complement. Even more interestingly, in 1988 two proofs
have been published independently of one another by
Immerman and Szelepcsényi, respectively. So, we continue
with the Immerman–Szelepcsényi Theorem.
Theorem 4 (Immerman–Szelepcsényi)co-NSPACE(f(n)) = NSPACE(f(n)) for every S-constructible
bounding function f satisfying f(n) > log n for all n ∈ N.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem II
Proof. Let L ∈ NSPACE(f(n)) be witnessed, without loss ofgenerality, by a nondeterministic 2-tape TM M = [B, Z, A] withSM (n) 6 f(n) for all n ∈ N.
Let Cx denote the set of f(|x|)-space bounded configurations of
M on input x. Note that
|Cx | 6 |Z| ·|B|f(|x|)+1 − 1· f(|x|) .
|B| − 1Furthermore, we write Cx (τ) to denote the set of configurations
that can be reached by M on input x within precisely τ steps ofcomputation. For the ease of notation, we write cx (τ) to denotethe cardinality of Cx (τ), i.e., cx (τ) = |Cx (τ)|.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem III
Without loss of generality, we can also assume that there is auniquely determined accepting configuration Ca and that M
works in each of its computations on input x exactly t steps,
where t 6 |Cx |. The proof of this statement is an exercise.
Then we have
M does not accept x

iff

Ca < Cx (t)iffCx (t) contains cx (t) many rejecting
final configurations.

The latter observation can be generalized to
Ca < Cx (τ)

iffCx (τ) contains
cx (τ) many configurations C 0 , Ca . (1)Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IV
Note that the time needed to check Condition (1) is at leastcx (τ) which is clearly exponential in τ.
We have to construct an NTM M 0 that accepts L (= Σ∗ \ L) in
space at most f(n).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IV
Note that the time needed to check Condition (1) is at leastcx (τ) which is clearly exponential in τ.
We have to construct an NTM M 0 that accepts L (= Σ∗ \ L) in
space at most f(n).
The idea for the construction of M 0 is given by theEquivalence (1) displayed above. Having the additional
information cx (τ) on hand, one can decide
nondeterministically in space f(|x|) whether or not Ca ∈ Cx (τ).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IV
Note that the time needed to check Condition (1) is at leastcx (τ) which is clearly exponential in τ.
We have to construct an NTM M 0 that accepts L (= Σ∗ \ L) in
space at most f(n).
The idea for the construction of M 0 is given by theEquivalence (1) displayed above. Having the additional
information cx (τ) on hand, one can decide
nondeterministically in space f(|x|) whether or not Ca ∈ Cx (τ).
Let C0 (x) denote the initial configuration of M on input x. If
x < L, the positive answer is easily obtained by guessing asequence of configurations C1 , . . . , Cτ such that C1 = C0 (x) andCi+1 is reachable by M in one step from Ci , and Cτ = Ca .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem V
Of course, we have to do this guessing iteratively. That is, wealways have at most two configurations on the work tape. Thiscan be easily achieved by deleting Ci−1 as soon as Ci isgenerated and verified. Again, for the sake of notation, we
write Ci ` Ci+1 if Ci+1 can be reached by M in one step.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem V
Of course, we have to do this guessing iteratively. That is, wealways have at most two configurations on the work tape. Thiscan be easily achieved by deleting Ci−1 as soon as Ci isgenerated and verified. Again, for the sake of notation, we
write Ci ` Ci+1 if Ci+1 can be reached by M in one step.
For the negative answer, we successively check for C 0 ∈ Cx
with C 0 , Ca whether C 0 ∈ Cx (τ). The number of positive
answers is counted (that is the reason, why we needf(n) > log n). If we find cx (τ) many such configurations C 0 , wemust conclude Ca < Cx (τ).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem V
Of course, we have to do this guessing iteratively. That is, wealways have at most two configurations on the work tape. Thiscan be easily achieved by deleting Ci−1 as soon as Ci isgenerated and verified. Again, for the sake of notation, we
write Ci ` Ci+1 if Ci+1 can be reached by M in one step.
For the negative answer, we successively check for C 0 ∈ Cx
with C 0 , Ca whether C 0 ∈ Cx (τ). The number of positive
answers is counted (that is the reason, why we needf(n) > log n). If we find cx (τ) many such configurations C 0 , wemust conclude Ca < Cx (τ).
All what is left is to formalize this idea appropriately.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem VI
We define a procedure REACH. On input τ, c, C1 , . . . , Cτ , REACH tries todecide whether at least one of the configurations C1 , . . . , Cτ is in
Cx (τ). If REACH does not succeed, it returns “?”. The parameter c isused to estimate the cardinality of Cx (τ).
Procedure REACH(τ, c, C1 , . . . , Cτ )Input: τ, c ∈ N, {C1 , . . . , Cτ } ⊆ Cx
Output: true, false or ?
Method: number := 0;
for C ∈ Cx in lexicographical order do begin
guess nondeterministically a computation
C0 (x) ` D1 ` · · · ` Dτ of length τ;
if Dτ = C then number := number + 1;
if Dτ ∈ {C1 , . . . , Cτ } then return REACH(τ, c, C1 , . . . , Cτ ) = true;end;
if number = c then return REACH(τ, c, C1 , . . . , Cτ ) = false;
if number < c then return REACH(τ, c, C1 , . . . , Cτ ) = ?;end REACH
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem VII
Now, we can show the following lemma:
Lemma 2
If procedure REACH is called with c = cx (τ) and REACH returns trueor false then this answer is correct.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem VII
Now, we can show the following lemma:
Lemma 2
If procedure REACH is called with c = cx (τ) and REACH returns trueor false then this answer is correct.
Proof. First, assume true is returned. This can happen if andonly if REACH has found an initial segment
C0 (x) ` D1 ` · · · ` Dτ of a computation such thatDτ ∈ {C1 , . . . , Cτ }. So, the answer is correct.
Next, assume false is returned. Then we havenumber = c = cx (τ), i.e., REACH has found c many different
configurations none of which is equal to one of the Ci s. By
definition of cx (τ) this implies that all configurations in Cx (τ)
have been tested, thus Cx (τ) ∩ {C1 , . . . , Cτ } = ∅. Hence, theanswer is correct.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IX

If REACH returns ? for c = cx (τ), then not all configurations
C ∈ Cx (τ) have been found in the for-loop. Therefore, one canneither conclude Ci < Cx (τ) nor Ci ∈ Cx (τ).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IX

If REACH returns ? for c = cx (τ), then not all configurations
C ∈ Cx (τ) have been found in the for-loop. Therefore, one canneither conclude Ci < Cx (τ) nor Ci ∈ Cx (τ).
Since number 6 |Cx |, one can represent number in space O(f(|x|).
Moreover, every configuration C ∈ Cx (τ) needs space at mostf(|x|), and thus REACH can be realized by an NTM that obeys thespace bound f(n).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem IX

If REACH returns ? for c = cx (τ), then not all configurations
C ∈ Cx (τ) have been found in the for-loop. Therefore, one canneither conclude Ci < Cx (τ) nor Ci ∈ Cx (τ).
Since number 6 |Cx |, one can represent number in space O(f(|x|).
Moreover, every configuration C ∈ Cx (τ) needs space at mostf(|x|), and thus REACH can be realized by an NTM that obeys thespace bound f(n).
Next, we have to deal with the question how the numbers cx (τ)
are determined. This is done iteratively by the following
procedure COUNT:

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem X
Procedure COUNT(τ, c)Input: τ, c ∈ N
Output: d ∈ N or ?
Method: d := 0;
for C ∈ Cx in lexicographical order do begin
compute the direct predecessors C1 , . . . , Cτ of C;z := REACH(τ − 1, c, C1 , . . . , Cτ );if z = true then d := d + 1;
if z = ? then return COUNT(τ, c) = ?;end;
return COUNT(τ, c) := d;end COUNT.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XI
Lemma 3
If COUNT is called with c = cx (τ − 1) and returns a natural
number d, then d = cx (τ).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XI
Lemma 3
If COUNT is called with c = cx (τ − 1) and returns a natural
number d, then d = cx (τ).
Proof. If COUNT is not stopping with output “?” received from
REACH, then, by Lemma 2, REACH correctly answers eachquestion whether one of the predecessors Ci of C belongs to
Cx (τ − 1). Thus, after completion of the for-loop, the value of dcoincides with |Cx (τ)|, since every C ∈ Cx (τ) must have apredecessor in Cx (τ − 1).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XI
Lemma 3
If COUNT is called with c = cx (τ − 1) and returns a natural
number d, then d = cx (τ).
Proof. If COUNT is not stopping with output “?” received from
REACH, then, by Lemma 2, REACH correctly answers eachquestion whether one of the predecessors Ci of C belongs to
Cx (τ − 1). Thus, after completion of the for-loop, the value of dcoincides with |Cx (τ)|, since every C ∈ Cx (τ) must have apredecessor in Cx (τ − 1).
Moreover, it is easy to verify that COUNT can be executed inspace O(f(|x|)).
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XII

Now, we can put this all together to decide
nondeterministically whether or not M, on input any x does notpossess an accepting computation.
On input x do the following:cx (0) := 1;for τ = 1, . . . , t do
if cx (τ − 1) , ? then cx (τ) := COUNT(τ, cx (τ − 1));else cx (τ) := ? ;if cx (τ) , ? then z := REACH(t, cx (t), Ca );if z = false then accept x.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XIIIThis program part can be executed by an NTM M 0 in spaceO(f(|x|)), too.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XIIIThis program part can be executed by an NTM M 0 in spaceO(f(|x|)), too.
Furthermore, if M 0 is accepting an input x, then there must be acomputation path of M 0 such that neither REACH nor COUNT doreturn “?”. Hence, COUNT correctly computes the values cx (τ)
for τ = 1, . . . , t and REACH verifies that Ca < Cx (t).
Consequently, x < L, thus x ∈ L and we are done.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XIV
Finally, if x < L, then for every configuration C ∈ Cx (τ) there is partial
computation C0 (x) ` D1 ` · · · ` Dτ = C that can be guessed while
processing
REACH(τ, cx (τ), C1 , . . . , Cτ ) .
Consequently, COUNT is correctly computing the valuescx (1), . . . , cx (t), too. But then REACH(t, cx (t), Ca ) must return false.
Therefore, M 0 is accepting x.
Thus, we have shown that L ∈ co-NSPACE(f(n)) implies
L ∈ NSPACE(f(n)), i.e.,
co-NSPACE(f(n)) ⊆ NSPACE(f(n))
for all S-constructible bounding functions f satisfying f(n) > log n for
all n ∈ N. Hence, we can conclude
co-NSPACE(f(n)) = NSPACE(f(n))

by Exercise 3 below .

Note that the S-constructibility of f ensures that s = f(|x|) can be
determined by M 0 and thus, also t is known.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

The Immerman–Szelepcsényi Theorem XV
A closer look at the proof of Theorem 4 shows that an easy
modification at the end of the proof even allows for proving thefollowing more general corollary1 :Corollary 2
co-NSPACEmax (f(n)) ⊆ NSPACEmax (f(n)) for all bounding
functions f satisfying f(n) > log n for all n ∈ N.
We leave it as an exercise to show Corollary 2. Furthermore as
already mentioned in the proof of Theorem 4, the following
result always holds:
Exercise 3. For every complexity class C we have, if co-C ⊆ C thenco-C = C.
The complexity class NSPACEmax (f(n)) is obtained when “minimum” iseverywhere replaced by “maximum” in the Definition of S(w).
1Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Hierarchy for Nondeterministic Space

Now, it is easy to prove the following hierarchy result for
nondeterministic space:
Theorem 5
Let f, g : N → N be any two bounding functions such thatf(n) = o(g(n)), g(n) > log n for all n ∈ N and g is
S-constructible. ThenNSPACE(f(n)) ⊂ NSPACE(g(n)) .
The proof is left as an exercise.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

RemarkOne final remark is in order here. In all our hierarchy theorems,
we have always required the bounding function of the larger
complexity class to be constructible. This condition cannot be
dropped. For non-constructible functions one can prove nicegap theorems. For giving us a flavor, we finally include thefollowing exercise here:
Exercise 4. There are recursive functions f, g : N → N such that
(1)

TIME(f(n)) = TIME(2f(n) );(2)

SPACE(g(n)) = SPACE(22Complexity and Cryptography

g(n)

).

c Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA I
After having seen that nondeterministic space is closed undercomplement provided that the bounding function f satisfies
f(n) > log n for all n ∈ N, we can answer the question whether
or not the context-sensitive languages are closed undercomplement. This is done by characterizing CS in terms ofcomplexity theory.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA I
After having seen that nondeterministic space is closed undercomplement provided that the bounding function f satisfies
f(n) > log n for all n ∈ N, we can answer the question whether
or not the context-sensitive languages are closed undercomplement. This is done by characterizing CS in terms ofcomplexity theory.
Definition 1
A linear bounded automaton is a nondeterministic one-tape TM
such that(1) its input alphabet contains two special symbols ¶ and $which are used to mark the leftmost and rightmost positionof the tape, respectively, that can be reached by the head.
(2) The head can neither replace ¶ nor $.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA IISo, a linear bounded automaton can only use the space between
the two markers ¶ and $. The input is written between thesemarkers. Please note that the end-markers are written on thetape together with the input but are themselves not considered
to belong to the input. Now, taking Theorem 10.11 from Theoryof Computation into account, we can easily show the following:
Theorem 6
For every context-sensitive language L there is a linear bounded
automaton M such that L = L(M).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA III
Proof. First, we divide the tape into two traces. The upper tracecontains the input w which will not be changed during thecomputation. The lower trace is actually used to simulate apossible derivation of w provided it exists. Both traces are
uniformly marked by ¶ and $.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA III
Proof. First, we divide the tape into two traces. The upper tracecontains the input w which will not be changed during thecomputation. The lower trace is actually used to simulate apossible derivation of w provided it exists. Both traces are
uniformly marked by ¶ and $.
Let L = L(G), where G = [T , N, σ, P] is without loss of generality
length increasing. (cf. ToC, Theorem 10.11). If the input is λ, Mjust stops in its accepting state. If the input is not λ, M starts its
computation by writing σ on the leftmost place in the lower
trace. Then M guesses nondeterministically a derivation. If thederivation yields the input w, the input string w is accepted.
Otherwise, M stops without accepting the input.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA IVTo formalize this idea, we have to think about a way how thisnondeterministic guessing is performed. This is done byguessing a production and a position on the tape. From theproduction it can be derived how many cells are needed toreplace the nonterminal at the guessed position. If the guessed
position does not contain a nonterminal in the lower trace,nothing is done and a new guess is made. If there is a
nonterminal at the guessed position, the substring to the rightof the position is moved by the number of cells needed toreplace the nonterminal. If there is enough space to perform
this shift, then the replacement is done. If there is not enoughspace, then M stops without accepting.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA V

Finally, if a string has been derived that is precisely as long as
the input, it is compared with the input in the upper trace. Ifboth strings are identical, M accepts. Otherwise, it stops
without accepting. Since G is length increasing, there cannot bea derivation for w that exceeds the space between the markers ¶and $. Therefore, M accepts a string w if and only if w ∈ L(G).

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA V

Finally, if a string has been derived that is precisely as long as
the input, it is compared with the input in the upper trace. Ifboth strings are identical, M accepts. Otherwise, it stops
without accepting. Since G is length increasing, there cannot bea derivation for w that exceeds the space between the markers ¶and $. Therefore, M accepts a string w if and only if w ∈ L(G).
Interestingly enough, the converse direction is also true. Thatis, every language accepted by a linear bounded automaton iscontext-sensitive. Thus, we have the following result:Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA VI
Theorem 7
If L = L(M) for a linear bounded automaton M, then L ∈ CS.
The proof is not too hard and left as an exercise.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

LBA VI
Theorem 7
If L = L(M) for a linear bounded automaton M, then L ∈ CS.
The proof is not too hard and left as an exercise.
Thus we could characterize the context-sensitive languages as
the set of all those languages that are accepted by a linear
bounded automaton. Since a linear bounded automaton uses
space |w| + 2 on its tape, we can apply the
Immerman–Szelepcsényi Theorem and obtain the affirmative
answer to the problem whether or not CS is closed undercomplement.
Corollary 3
CS is closed under complement.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Important Complexity Classes I
Now, we are ready to introduce the following importantcomplexity classes:
L =df SPACE(log n) ;NL =df NSPACE(log n) ;[P =df TIME(nO(1) ) =TIME(nc ) ;c∈N

NP =df NTIME(n

O(1)

[

)=

NTIME(nc ) ;c∈N

PSPACE =df SPACE(nO(1) ) =[SPACE(nc ) ;c∈N

NPSPACE =df NSPACE(n

O(1)

)=

[

NSPACE(nc ) .

c∈NComplexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Important Complexity Classes II
We can immediately make the following observations:
Theorem 2(1) L ⊆ NL;(2) P ⊆ NP;(3) PSPACE ⊆ NPSPACE;(4) P ⊆ PSPACE;(5) NP ⊆ NPSPACE.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Important Complexity Classes II
We can immediately make the following observations:
Theorem 2(1) L ⊆ NL;(2) P ⊆ NP;(3) PSPACE ⊆ NPSPACE;(4) P ⊆ PSPACE;(5) NP ⊆ NPSPACE.
Moreover, we already know the following proper inclusion:
Theorem 8
L ⊂ PSPACE.
Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Important Complexity Classes III

Furthermore, one is often interested in simultaneously bounding
the time and space resources needed to accept a language.
Thus, we shall also study the following complexity classes:
DTISP(f(n), g(n)) =df {L(M) | M is a DTM ∧ TM (n) 6 f(n)∧ SM (n) 6 g(n)} ;NDTISP(f(n), g(n)) =df {L(M) | M is an NDTM
∧ TM (n) 6 f(n) ∧ SM (n) 6 g(n)} ;
PLOPS =df DTISP nO(1) , (log n)O(1) .

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Important Complexity Classes IV

Algorithms belonging to the complexity class PLOPS areconsidered to be practically realizable using current computer
technology. Nevertheless, even this statement has to be readwith care, since in practice one has also to ensure that theexponents and constants involved are moderate.

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Joel I. Seiferas

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Michael J. Fischer

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Albert R. Meyer

Complexity and Cryptographyc Thomas Zeugmann

Tape Reductions

Nonderterministic Time

Immerman–Szelepcsényi

LBA

ICC

End, Pics

Neil Immerman
Complexity and Cryptographyc Thomas Zeugmann