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}\).

Prove that an oracle \(C\) exists for which $\mathrm{NP}^{C} \neq \operatorname{coNP}^{C} .$

A k-query oracle Turing macbine is an oracle Turing machine that is permitted to make at most \(k\) queries on each input. A \(k\)-query oracle Turing machine \(M\) with an oracle for \(A\) is written \(M^{A, k}\). Define \(\mathrm{P}^{A, k}\) to be the collection of languages that are decidable by polynomial time \(k\)-query oracle Turing machines with an oracle for \(A\). a. Show that $\mathrm{NP} \cup \operatorname{coNP} \subseteq \mathrm{P}^{\mathrm{SAT}, 1}$. b. Assume that \(\mathrm{NP} \neq \operatorname{coNP}\). Show that $\mathrm{NP} \cup \operatorname{coNP} \subsetneq \mathrm{P}^{S A T, 1}$.

Give regular expressions with exponentiation that generate the following languages over the alphabet \(\\{0,1\\}\). A. All strings of length 500 \({ }^{A} \mathrm{~b} .\) All strings of length 500 or less A. All strings of length 500 or more A d. All strings of length different than 500 e. All strings that contain exactly \(5001 \mathrm{~s}\) f. All strings that contain at least 500 is g. All strings that contain at most 500 is h. All strings of length 500 or more that contain a 0 in the 500 th position i. All strings that contain two os that have at least 500 symbols between them

^{*}\( that is defined as follows. Let \)p a d(s, l)=s \\#^{3}\(, where \)j=\max (0, l… # Consider the function pad: $\Sigma^{*} \times \mathcal{N} \longrightarrow \Sigma^{*} \\#^{*}\( that is defined as follows. Let \)p a d(s, l)=s \\#^{3}$, where \(j=\max (0, l-m)\) and \(m\) is the length of \(s\). Thus, pad \((s, l)\) simply adds enough copies of the new symbol # to the end of \(s\) so that the length of the result is at least \(l .\) For any language \(A\) and function $f: \mathcal{N} \longrightarrow \mathcal{N}\(, define the language \)p a d(A, f)$ as \(p a d(A, f)=\\{p a d(s, f(m)) \mid\) where \(s \in A\) and \(m\) is the length of \(s\\} .\) Prove that if \(A \in \operatorname{TIME}\left(n^{6}\right)\), then $\operatorname{pad}\left(A, n^{2}\right) \in \operatorname{TIME}\left(n^{3}\right) .$

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) .$