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.
〈G, s, t, d〉, where G is an undirected graph, s and t are nodes in G, and d is a positive integer.
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 ∈ 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(n³) = coNSPACE(n³). See Problem 9.13, in the textbook for a description of padding.
4. Show that TQBF /∈ SPACE(n 1/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.