# 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!)

(Omit!)