Answer each part TRUE or FALSE. a. \(n=o(2 n)\). A \(\mathbf{d .} \quad 1=o(n)\). b. \(2 n=o\left(n^{2}\right)\). e. \(n=o(\log n)\). A c. \(2^{n}=o\left(3^{n}\right)\). f. \(1=o(1 / n)\).

Let \(D O U B L E-S A T=\\{\langle\phi\rangle \mid \phi\) has at least two satisfying assignments \(\\}\). Show that DOUBLE-SAT is NP-complete.

Let \(A \subseteq 1^{*}\) be any unary language. Show that if \(A\) is NP- complete, then \(\mathrm{P}=\mathrm{NP}\). (Hint: Consider a polynomial time reduction \(f\) from \(S A T\) to \(A\). For a formula \(\phi\), let \(\phi_{0100}\) be the reduced formula where variables \(x_{1}, x_{2}, x_{3}\), and \(x_{4}\) in \(\phi\) are set to the values \(0,1,0\), and 0 , respectively. What happens when you apply \(f\) to all of these exponentially many reduced formulas?)

Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem \(7.16\) for string \(w=\) baba and CFG \(G\) : $$ \begin{aligned} &S \rightarrow R T \\ &R \rightarrow T R \mid \mathrm{a} \\ &T \rightarrow T R \mid \mathrm{b} \end{aligned} $$

Show that \(P R I M E S=\\{m \mid m\) is a prime number in binary \(\\} \in\) NP. (Hint: For \(p>1\), the multiplicative group \(Z_{p}^{*}=\\{x \mid x\) is relatively prime to \(p\) and \(1 \leq x

Let \(M O D E X P=\\{\langle a, b, c, p\rangle \mid a, b, c\), and \(p\) are positive binary integers such that \(\left.a^{b} \equiv c(\bmod p)\right\\}\). Show that \(M O D E X P \in P\). (Note that the most obvious algorithm doesn't run in polynomial time. Hint: Try it first where \(b\) is a power of 2 .)