dr. Peter van Emde Boas
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
-- 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.
The topological Sort problem. Design an O(n+e) algorithm for numbering
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.
(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?
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
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
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
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.
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.
Show that RE languages L can be enumerated without repeating
elements in L.
What happens if L is finite ?
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.
Show that the eight functions listed are constructible; space
constructability in cases i to iv, and time
constructability for the remaining cases.
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.
Show that the classes P and NP are closed under Kleene
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.
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.