NOTE: Each problem set counts 15% of your mark, and it is important to do your own

work. You may consult with others concerning the general approach for solving problems on

assignments, but you must write up all solutions entirely on your own. Copying assignments

is a serious academic offense and will be dealt with accordingly.

1. The decision problem PARTITION is defined on page 13 of the Notes NP and NPCompleteness". (You may assume that a1; : : : am are positive integers.)

Define the associated search problem PARTITION-SEARCH and give an algorithm

showing that

PARTITION-SEARCH ! p PARTITION.

Give a loop invariant for your algorithm.

(See Definition 6 in the Notes Search and Optimization Problems" for the definition

of ! p .)

2. Consider the problem DISTANCE-PATH.

DISTANCE-PATH

Instance

hG; s; t; di, where G is an undirected graph, s and t are nodes in G, and d is a positive

integer.

Question Is the distance from s to t exactly d? In other words, is it the case that there

is a path of length d from s to t, and no shorter path from s to t?

(a) Show that DISTANCE-PATH 2 NL.

(b) Show that DISTANCE-PATH is NL-complete.

Hint: Show that P AT H =L DISTANCE-PATH. Given a directed graph G construct

an undirected graph G0 by making n copies of G. Each edge in G0 goes from copy i to

copy i + 1.

3. Use a padding argument to show that NL = coNL implies NSPACE(n3) = coNSPACE(n3).

See Problem 9.13, in the textbook for a description of padding.

4. Show that T QBF = 2 DSPACE(n1=5). You may refer to the proof of Theorem 8.9 in

the text, and assume the fact that the reduction presented there can be carried out in

log space.

1