__dr. Peter van Emde Boas__

**EXCERCISES**

**All excercises, unless indicated
otherwise, are selected from our text**
**Computational Complexity by
C.H. Papadimitriou.**

**Answers should be returned by
the suggested deadline of May 06 2003,**
**preferably on paper. Based on
previous experience and troubles**
**electronic submission is discouraged
and may be rejected as soon as I have**
**problems with downloading or
printing the material.**

**Cooperation between students
is permitted under the following conditions:**

**-- the group shoudn't exceed
three people.**
**-- the cooperation must be clearly
indicated on all solutions submitted**
**-- a group starting to cooperate
must persist in this cooperation till the end**
** of the course.**
**-- the group will be graded
as a collective; it is the responsibility of the**
** people cooperating
to prevent abuses.**

**Chapter 1.**

**1.4.4
The topological Sort problem. Design an O(n+e) algorithm for numbering
the nodes**
**
of an Acyclig Graph in such a way that all edges go from a lower to a higher
numbered node,**
**
or reports that such a numbering doesn't exist by finding a Cycle.**

**1.4.15
(parts a and b only)**
**
Develop the Dynamic programming Algorithm for the TSP suggested in the
excercise.**
**
Why is this an improvement over the naive enumeration of all possible tours?**

**Chapter 2.**

**2.8.8
This excercise involves a version of the Turing Machine where symbols can
be insterted and**
**
deleted, rather than rewritten.**
**
Do parts (a) and (b) of the excercise.**
**
Next show that the k-work-tape version can be simulated with constant delay
by a Turing Machine**
**
equipped with 2k stacks as working storage.**
**
Show that these simulations are constant factor overhead in space.**

**2.A (Not in book)
Consider a version of the Turing Machine where the number of heads on a
single tape can be**
**
2 or greater. The number of heads on each tape is fixed (independent
of the input and the**
**
moment of time during the computation). The heads move independently during
the excecution**
**
of an instruction.**
**(a)
The model exhibits the problem of write conflicts: what happens if two
heads attempt to write**
**
different symbols at the same location on the tape. Formulate a workable
proposal for eliminating this risk.**
**(b)
Show how to simulate this device with constant factor delay by a device
where during each instruction**
**
just one head moves.**
**(c)
Show how to simulate this version on a standard multi-tape machine. What
are the obtained**
**
overheads in time and space?**

**Remark: There are simulations
in the litereature which solve this excercise with contstant delay in time.
I do not**
**expect you to find such a solution
but you can always try.....**

**2.B (Not in book)
Show how to simulate a Turing machine whose worktape is organised like
a complete binary tree by a standard**
**
machine using linear tapes only. I.E., the machine can perform three moves
on the tree: up, left or right;**
**
at the root of the tree the machine will observe that it is at the root
and it can't move up.**
**
Evidently the number of cells accessible in k steps now grows
exponentially in k; is this feature the cause of the**
**
machine to become exponentially faster than the standard device?**

**2.C (Not in book)
Show how to simulate on a standard RAM a version of the RAM which has access
to k**
**
memories (k fixed). The simulation should be constant
factor overhead both in time and space.**
**
Keep in mind to use the right space measure!**
**
Can you generalize this simulation so that it can simulate a potential
infinite number of RAM memories?**

**2.D (Not in the book)
There exists a classic trick to simulate initialized RAM memory on an uninitialized
RAM.**
**
The idea is to represent RAM register R[i] by a pair of reisters
R'[2i] and R'[2i+1] . The first**
**
word stores the simulated content of R[i], whereas the second word stores
a pointer towards**
**
an address S[j] in yet another mermory bank where a backward
pointer towards R'[2i+1]**
**
is located. This pair of pointers validates that R'[2i] has been
properly allocated and used.**
**
If a new location is used for the first time a next entry in the S-memory
bank is allocated and**
**
propery initialized.**

**
Work out the details of this simulation. Formally state the required invariants.
Next show that this**
**
simulation has linear time overhead and constant factor space overhead
provided the correct space**
**
measure is used.**

**Remark: this excercise is derived
from a similar excecrcise in the 1974 textbook of Aho, Hopcroft and Ullman**
*The design and analysis of
algorithms*, chapter 2, excercise 2.12.

**Chapter 3.**

**3.4.1
Solve the instances a, b, c, and d of this problem.
Next solve the additional instance h:**
**
h: Given a Turing Machine M , input x and
a number k, will the machine on input x**
**
enter at least k different states during its computation.**

**3.4.4
Show that RE languages L can be enumerated without repeating
elements in L.**
**
What happens if L is finite ?**

**3.4.5
Show that an RE languages L which can be enumerated in increasing
order is recursive.**
**
Again be careful about what happens in the case that L is finite.**

**Chapter 7.**

**7.4.3
Show that the eight functions listed are constructible; space
constructability in cases i to iv, and time**
**
constructability for the remaining cases.**

**7.4.4
Analyse the six classes of functions mentioned for the properties
of left and right polynomial composition.**
**
Also give a more elaborate justification for the intuitive relevance of
these two properties stated by**
**
Papadimitriou: model independence for closure under left composition and
closure under reductions for**
**
closure under right composition.**

**7.4.6
Show that the classes P and NP are closed under Kleene
star.**
**
Hint: for the case P consider the subproblem of checking
efficiently whether an input string x can be entirely**
**
decomposed in substrings in a language A, given some efficient
oracle for testing membership in A.**
**
Think about dynamic programming.**

**Chapter 8.**

**8.4.3
We restrict ourselves to two versions of many one reductions: Polynomial
time and Logspace.**
**
Investigate which of the seven classes listed are closed under these two
reductions.**
**
Explain why Time(n ^{2}) is not closed under reductions.**