DEADLINE FOR ALL BONUS ASSIGNMENTS IS JAN 16, 2006. THIS IS A HARD NON-NEGOTIABLE DEADLINE.
Assignment 8.4.4 (only the first part concerning reduction of the languages in TIME(f(n))).
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.)
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'?
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)
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.