34.3 NP-completeness and reducibility

34.3-1

Verify that the circuit in Figure 34.8(b) is unsatisfiable.

(Omit!)

34.3-2

Show that the $\le_\text P$ relation is a transitive relation on languages. That is, show that if $L_1 \le_\text P L_2$ and $L_2 \le_\text P L_3$, then $L_1 \le_\text P L_3$.

(Omit!)

34.3-3

Prove that $L \le_\text P \bar L$ if and only if $\bar L \le_\text P L$.

(Omit!)

34.3-4

Show that we could have used a satisfying assignment as a certificate in an alternative proof of Lemma 34.5. Which certificate makes for an easier proof?

(Omit!)

34.3-5

The proof of Lemma 34.6 assumes that the working storage for algorithm A occupies a contiguous region of polynomial size. Where in the proof do we exploit this assumption? Argue that this assumption does not involve any loss of generality.

(Omit!)

34.3-6

A language $L$ is complete for a language class $C$ with respect to polynomial-time reductions if $L \in C$ and $L' \le_\text P L$ for all $L' \in C$. Show that $\emptyset$ and $\{0, 1\}^*$ are the only languages in $\text P$ that are not complete for $\text P$ with respect to polynomial-time reductions.

(Omit!)

34.3-7

Show that, with respect to polynomial-time reductions (see Exercise 34.3-6), $L$ is complete for $\text{NP}$ if and only if $\bar L$ is complete for \text{co-NP}\$.

(Omit!)

34.3-8

The reduction algorithm $F$ in the proof of Lemma 34.6 constructs the circuit $C = f(x)$ based on knowledge of $x$, $A$, and $k$. Professor Sartre observes that the string $x$ is input to $F$, but only the existence of $A$, $k$, and the constant factor implicit in the $O(n^k)$ running time is known to $F$ (since the language $L$ belongs to $\text{NP}$), not their actual values. Thus, the professor concludes that $F$ can't possibly construct the circuit $C$ and that the language $\text{CIRCUIT-SAT}$ is not necessarily $\text{NP-hard}$. Explain the flaw in the professor's reasoning.

(Omit!)