Complexity and Computation Theory 2003

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 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.