# 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

- 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.
- Sipser's text problem 10.5 page 378. (The majority function is
1 if at least half its inputs are 1.)
- Sipser's text problem 10.7 page 378.
- Sipser's text problem 5.10 page 195.
- Sipser's text problem 7.19 page 272.
- The PARTITION problem asks, given a collection of non-negative
binary numbers y
_{1},..., 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_{1},..., 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.

- 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.
- {< M,w> | Turing machine M accepts w}.
- {< M,w > | Turing machine M accepts w in at most |w|
^{2} steps}
- {< M,w > | Turing machine M accepts w in at most 2
^{|w|} steps}
- {< M,w> | Turing machine M does not accept w}
- {< F> | F is a 3-CNF formula which evaluates to true on some
truth assignment}
- {< F,x> | F is a 3-CNF formula which evaluates to true on truth
assignment x}
- {< F> | F is a propositional logic tautology}.
- {< G,k> | undirected graph G has a cycle of length at most k}