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

〈G, s, t, d〉, 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 ∈ 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.

## Reviews

There are no reviews yet.