Describe the error in the following fallacious "proof" that $\mathrm{P} \neq \mathrm{NP}\(. Assume that \)\mathrm{P}=\mathrm{NP}$ and obtain a contradiction. If \(\mathrm{P}=\mathrm{NP}\), then \(S A T \in \mathrm{P}\) and so for some \(k\), \(S A T \in T I M E\left(n^{k}\right)\). Because every language in NP is polynomial time reducible to \(S A T\), you have NP $\subseteq \operatorname{TIME}\left(n^{k}\right) .\( Therefore, \)\mathrm{P} \subseteq \operatorname{TIME}\left(n^{k}\right) .$ But by the time hierarchy theorem, \(\operatorname{TIME}\left(n^{k+1}\right)\) contains a language that isn't in \(\operatorname{TIME}\left(n^{k}\right)\), which contradicts $\mathrm{P} \subseteq \operatorname{TIME}\left(n^{k}\right)\(. Therefore, \)\mathrm{P} \neq \mathrm{NP}$.

(a) Let \(A\) be any language and \(k \in \mathcal{N}\). If \(A \in \mathrm{P}\), then \(\operatorname{pad}\left(A, n^{k}\right) \in \mathrm{P}\) because you can determine whether \(w \in p a d\left(A, n^{k}\right)\) by writing \(w\) as $s \\#^{l}\( where \)s$ doesn't contain the # symbol, then testing whether \(|w|=|s|^{k}\); and finally testing whether \(s \in A\). Implementing the first test in polynomial time is straightforward. The second test runs in time poly \((|s|)\), and because \(|s| \leq|w|\), the test runs in time poly \((|w|)\) and hence is in polynomial time. If $\operatorname{pad}\left(A, n^{k}\right) \in \mathrm{P}\(, then \)A \in \mathrm{P}\( because you can determine whether \)w \in A\( by padding \)w\( with # symbols until it has length \)|w|^{k}$ and then testing whether the result is in \(\operatorname{pad}\left(A, n^{k}\right)\). Both of these actions require only polynomial time. (b) Assume that \(\mathrm{P}=\operatorname{SPACE}(n)\). Let \(A\) be a language in \(\operatorname{SPACE}\left(n^{2}\right)\) but not in \(\operatorname{SPACE}(n)\) as shown to exist in the space hierarchy theorem. The language \(\operatorname{pad}\left(A, n^{2}\right) \in \operatorname{SPACE}(n)\) because you have enough space to run the \(O\left(n^{2}\right)\) space algorithm for \(A\), using space that is linear in the padded language. Because of the assumption, \(p a d\left(A, n^{2}\right) \in \mathrm{P}\), hence $A \in \mathrm{P}\( by part (a), and hence \)A \in \operatorname{SPACE}(n)$, due to the assumption once again. But that is a contradiction.

Prove that if NEXPTIME \(\neq\) EXPTIME, then \(P \neq N P\). You may find the function pad, defined in Problem \(9.13\), to be helpful.

Define the unique-sat problem to be \(U S A T=\\{\langle\phi\rangle \mid \phi\) is a Boolean formula that has a single satisfying assignment \(\\}\). Show that \(U S A T \in \mathrm{P}^{S A T}\).

The containment TIME $\left(2^{n}\right) \subseteq \operatorname{TIME}\left(2^{2 n}\right)\( holds because \)2^{n} \leq 2^{2 n}$. The containment is proper by virtue of the time hierarchy theorem. The function \(2^{2 n}\) is time constructible because a TM can write the number 1 followed by \(2 n\) os in \(O\left(2^{2 n}\right)\) time. Hence the theorem guarantees that a language \(A\) exists that can be decided in $O\left(2^{2 n}\right)\( time but not in \)o\left(2^{2 n} / \log 2^{2 n}\right)=o\left(2^{2 n} / 2 n\right)\( time. Therefore, \)A \in \operatorname{TIME}\left(2^{2 n}\right)\( but \)A \notin \operatorname{TIME}\left(2^{n}\right) .$

Give a circuit that computes the parity function on three input variables and show how it computes on input \(011 .\)