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(n2) is not closed under reductions.