Cook's Theorem

Show that if $P=\mathrm{NP}$, then all nonempty proper subsets $A$ of $\Sigma^{*}$ are NP-complete.

If $A$ is known to be $\mathrm{NP}$-complete, is $A^{2}$ always $\mathrm{NP}$-complete?

In the proof of Cook's theorem, we have used conditions (4.1) $-(4.5)$ on ???-shaped windows over matrix $S$ to satisfy condition (4). Show that if we, instead, work with ???-shaped windows over matrix $S$, then no conditions on these windows can satisfy condition (4). In other words, show that the following relation does not hold for any subset $T \subseteq \left(\Gamma^{\prime }\right)^{4}$ :

where $\alpha_{i}$ denotes the $i$ th configuration corresponding to the assignments to variables $y_{i, j, a}$.

Show that, in the proof of Cook's theorem, function $f_{1}$ is necessary. That is, no definition of subset $T$ can make the following true: $F_{x}^{\prime }=f_{0} f_{2} f_{3} f_{4}$ is satisfiable if and only if $x \in L(M)$.

In the proof of Cook's theorem, it is possible to remove condition (1), as long as we replace condition (4') by a new condition (4'') over six-square, ???-shaped windows. Find the subconditions over the six-square, ???-shaped windows that make $\left(4^{\prime \prime }\right)$ equivalent to condition (4), without the assumption of condition (1).

A Boolean formula which is a product of literals is called an elementary product. A DNF (disjunctive normal form) is a sum of elementary products.

Assume that $A$ and $B$ are two $\mathrm{NP}$-complete sets. Show that $A \cup B$ and $A \cap B$ are not necessarily $\mathrm{NP}$-complete, if $P \neq \mathrm{NP}$. Is $A \cup B$ always $\mathrm{NP}$-complete when $A \cap B=\emptyset$?

This exercise follows the notations defined in Exercise 3 of Section 7.1.

Assume that $P \neq \mathrm{NP}$. Let $A$ and $B$ be two sets that are complete for $c o-\mathrm{NP}$ (i.e., $\bar{A}$ and $\bar{B}$ are NP-complete). Is $A B$ necessarily in co-NP? Is $A B$ necessarily co-NP-complete? Is it possible that $A B$ is in $P$? Justify your answer.

Suppose that, in the proof of Cook's theorem, we drop condition (1) and replace condition $\left(4^{\prime }\right)$ by $(\overline{4})$, which specifies some subconditions on five-square windows of one of the four shapes shown in Figure 7.11. Show that no such subconditions on the five-square windows can make (4) equivalent to $\left(4^{\prime }\right)$.

Consider the alternative proof of Cook's theorem given in Example 7.33. Let $T \subseteq \left(\Gamma^{\prime }\right)^{6}$ be the set corresponding to the twelve windows of Figure 7.10; that is, $(a, b, c, d, e, g) \in T$ if and only if $(a, b, c, d, e, g)$ is in one of the twelve forms in Figure 7.10, and satisfies the corresponding conditions given in the three cases. Show that if there exists a mapping $\phi :\left(\Gamma^{\prime }\right)^{3} \rightarrow \left(\Gamma^{\prime }\right)^{3}$ such that $(a, b, c, d, e, g) \in T$ if and only if $\phi (a, b, c)= (d, e, g)$, then $L(M)$ is in $P$.

In this exercise, we consider a different setting for the proof of Cook's theorem. Instead of attaching the state symbol to the tape symbol currently scanned by the tape head, we may define separate Boolean variables to represent the state and the position of the tape head. That is, in addition to variables $y_{i, j, a}$ (for $a \in \Gamma$ only), we define, for each $i=0, \ldots , r(n)$ and each $q \in Q$, a variable $Q_{i, q}$ to mean that the state symbol of $\alpha_{i}$ is $q$, and for each pair $(i, j)$, with $i, j \in \left\{ 0, \ldots , r(n)\right\}$, a variable $H_{i, j}$ to mean that, in the configuration $\alpha_{i}$, the tape head is scanning the $j$ th symbol. To prove Cook's theorem in this setting, then we need to define six Boolean functions $g_{1}, \ldots , g_{6}$, such that, for $k=1, \ldots , 6, g_{k}=1$ if and only if the condition $(k)$ below holds:

(1) For each $i=0, \ldots , r(n), \alpha_{i}$ is in exactly one state.

(2) For each $i=0, \ldots , r(n)$, the head scans exactly one cell in $\alpha_{i}$.

(3) For each $i=0, \ldots , r(n)$ and each $j=0, \ldots , r(n)$, the $j$ th cell of $\alpha_{i}$ contains exactly one symbol.

(4) $\alpha_{0}$ is the initial configuration of $M$ on input $x$.

(5) $\alpha_{r(n)}$ is an accepting configuration.

(6) For each $i=0, \ldots , r(n)-1, \alpha_{i} \vdash \alpha_{i+1}$.

Assume that $g_{1}, \ldots , g_{5}$ satisfy the condition that $g_{k}=1$ if and only if condition $(k)$ holds. Also let $g_{6}$ be

where $\Delta =-1$ if $D=L$, and $\Delta =1$ if $D=R$. Find a counterexample to disprove that $G_{x}=\prod_{i=1}^{6} g_{i}=1$ if and only if $M$ accepts $x$. Find a new function $g_{6}$ satisfying that $G_{x}=1$ if and only if $M$ accepts $x$.