ps3

Problem Set 3

Assigned: Thursday, March 13, 2008
Due: Thursday, March 20, 2008

1.

Consider the following problem:

• Given a positive integer $M$, as well as a list of positive integers $x_1,\dots ,x_n$, find the closest you can get to $M$ by adding a subset of $x_i$‘s without exceeding $M$. In other words, find the maximum of

$$\sum _{i\in S}{x}_i$$

over all subsets $S\subseteq \{1,\dots ,n\}$ such that

$$\sum _{i\in S}{x}_i\le M.$$

In the general case — where $M$ could be much larger than $n$ — it is known that the above problem is NP-complete. On the other hand, describe an algorithm to solve this problem whose running time is a polynomial function of $M$ and $n$. [Hint: Use dynamic programming, the same basic technique we used in class to solve the Longest Increasing Subsequence problem. In other words, show how a solution to the whole problem can be built recursively out of solutions to a reasonable number of subproblems.]

2.

“The Equivalence of Search and Decision Problems.” Suppose there’s a polynomial-time algorithm to decide whether a given Boolean formula $\phi (x_1,\dots ,x_n)$ has a satisfying truth assignment. (In other words, suppose $P=NP$.) Show that this implies that we can actually find a satisfying assignment for any Boolean formula $\phi$ in polynomial time, whenever one exists. [Hint: Give an algorithm that constructs a satisfying assignment for $\phi$, one variable at a time, repeatedly calling the decision algorithm as an oracle.]

3.

Suppose problem $X$ is proved NP-complete, by a polynomial-time reduction that maps size-$n$ instances of $SAT$ to size-$n^3$ instances of problem $X$. And suppose that someday, some genius manages to prove that $SAT$ requires $\Omega (c^n)$ time, for some constant $c>1$. Then what can you conclude about the time complexity of problem $X$?

4.

Let $EXACT4SAT$ be the following problem:

• Given a Boolean formula $\phi$, consisting of an AND of clauses involving exactly 4 distinct literals each (such as $(x_2\vee \neg x_3\vee \neg x_5\vee x_6)$), decide whether $\phi$ is satisfiable.

Show that $EXACT4SAT$ is NP-complete. You can use the fact, which we proved in class, that $3SAT$ is NP-complete.