===========================================================================
CSC 363H              Tutorial Exercises for Week 12            Summer 2006
===========================================================================

 -  Explain why the following simpler algorithm works to show that Vertex
    Cover is polytime self-reducible.  (Hint: read the lecture summary for
    week 11 -- the point is to get you to do this, understand the material
    there, and ask questions if you don't.)

        VCS(G,k):
            if not VC(G,k):  return NIL
            C = {}  # the vertices in a vertex cover of G
            while k > 0:
                pick an unmarked vertex v in V
                if VC(G-v, k-1):
                    C = C U {v};  G = G - v;  k = k - 1
                else:  mark v
            return C

 -  Give a precise definition of PSPACE-completeness.  (Yes, I realize this
    is in the book -- again, the point is to make sure everyone has looked
    at it and understands it.)

 -  Show that for any function s(n), the class SPACE(s(n)) remains the same
    whether we define it in terms of the single-tape TM model or in terms
    of the k-tape TM model.

 -  Show that PSPACE is closed under union, star, and complementation.