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.
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.