T-79.240 Special Course on Computational Complexity

Extra Assignments/Autumn 2004


Below are 5 EXTRA BONUS assignments for the course. By solving bonus assignments you can increase your total points but they do not affect point limits for the grades. The bonus assignments are graded with the scale 0-1.5.

DEADLINE FOR ALL BONUS ASSIGNMENTS IS JAN 14, 2005. THIS IS A HARD NON-NEGOTIABLE DEADLINE.

  1. Assignment 8.4.4 (only the first part concerning reduction of the languages in TIME(f(n)))
  2. Show that the following problem is in \Sigma_2 P:
    INSTANCE: A set of clauses S and a variable x
    QUESTION: Is there a truth assignment that is minimal for S and satisfies x?
    (A truth assignment T is minimal for a set of clauses S if T satisfies S and there is no other truth assignment T' which is smaller, i.e., for which T'(y) = true implies T(y) = true for all variables y.)
  3. Show that the following problem 'EXACT COVER BY 4-SETS' is NP-complete:
    INSTANCE: Finite set X with |X|=4q, q an integer, and a collection C of 4-element subsets of X
    QUESTION: Is there a subcollection C' of C such that every element of X occurs in exactly one member of C'?
  4. Show that the following problem 'SET SPLITTING' is NP-complete:
    INSTANCE: Collection C of subsets of a finite set S
    QUESTION: Is there a partition of S into two subsets S1 and S2 such that no subset in C is entirely contained in either S1 or S2?
    (Hint: use 3NAESAT)
  5. Show that the following problem is PSPACE-complete:
    INSTANCE: A deterministic Turing machine M and an integer k
    QUESTION: Does there exist an input x of length k such that M accepts x without ever leaving the k+1 first symbols of its string.