CSEP 590TU Assignment #8
Autumn 2003

Due: Wednesday, Dec 3, 2003.

Read Chapter 10, sections 10.2, 10.4 and 10.6 of Sipser's text. (Ignore the proof of Lemma 10.5!)

Problems

1. Sipser's text problem 8.19. Only the part of showing that the problem is in NL is required. The NL-hardness is a bonus if you would like to do it.

2. Sipser's text problem 10.5 page 378. (The majority function is 1 if at least half its inputs are 1.)

3. Sipser's text problem 10.7 page 378.

4. Sipser's text problem 5.10 page 195.

5. Sipser's text problem 7.19 page 272.

6. The PARTITION problem asks, given a collection of non-negative binary numbers y₁,..., y_n whether or not it is possible to partition these numbers into two groups so that the sum in each group is the same. More formally,
   PARTITION={< y₁,..., y_n> | there is a subset S in {1,.., n} so that the sum of all y_i for i in S equals the sum of all y_j for j not in S}

   Prove that PARTITION is NP-complete. Give a reduction from SUBSET-SUM and try adding two large numbers of appropriate sizes to your set.

7. For each of the following languages determine whether the problem is (i) Turing-recognizable, (ii) decidable, (iii) in PSPACE, (iv) in NP, (v) NP-hard, or (vi) in P. It might be more than one (or none) so you should answer Yes, No, or Don't Know for each of these possibilities. Briefly justify each answer.

   1. {< M,w> | Turing machine M accepts w}.

   2. {< M,w > | Turing machine M accepts w in at most |w|² steps}

   3. {< M,w > | Turing machine M accepts w in at most 2^|w| steps}

   4. {< M,w> | Turing machine M does not accept w}

   5. {< F> | F is a 3-CNF formula which evaluates to true on some truth assignment}

   6. {< F,x> | F is a 3-CNF formula which evaluates to true on truth assignment x}

   7. {< F> | F is a propositional logic tautology}.

   8. {< G,k> | undirected graph G has a cycle of length at most k}