Let's say a language $L \subseteq \{0,1\}^*$ is in $\textbf{P}_{angel}$ if there exists a polynomial $p : \mathbb{N} \mapsto \mathbb{N}$, a sequence of strings $\{\alpha_n\}_{n \in \mathbb{N}}$ with $\alpha_n \in \{0,1\}^{p(n)}$, and a deterministic polynomial time Turing Machine $M$ such that for every $x \in \{0,1\}^n$ $$x \in L \Leftrightarrow M(x, \alpha_n) = 1$$ Let us call $\alpha_n$ to be the [i]angel string [/i]for all $x$ of the length $n$. Note that the [i]angel string[/i] is $\textbf{not}$ similar to a [i]witness[/i] or [i]certificate [/i]as used in the definition of $\textbf{NP}$ For example, all unary languages, even $UHALT$ which is undecidable, are in $\textbf{P}_{angel}$ because the \textit{angel string} can simply be a single bit that tells us if the given unary string is in $UHALT$ or not. \\\\ A set $S \subseteq \Sigma^*$ is said to be [b]sparse[/b] if there exists a polynomial $p : \mathbb{N} \mapsto \mathbb{N}$ such that for each $n \in \mathbb{N}$, the number of strings of length $n$ in $S$ is bounded by $p(n)$. In other words, $|S^{=n}| \leq p(n)$, where $S^{=n} \subseteq S$ contains all the strings in $S$ that are of length $n$. [list=1] [*] Given $k \in \mathbb{N}$ sparse sets $S_1, S_2 \ldots S_k$, show that there exists a sparse set $S$ and a deterministic polynomial time TM $M$ with oracle access to $S$ such that given an input $\langle x,i \rangle$ the TM $M$ will accept it if and only if $x \in S_i$. \\Define the set $S$ (note that it need not be computable), and give the description of $M$ with oracle $S$. \\Note that a TM $M$ with oracle access to $S$ can query whether $s \in S$ and get the correct answer in return in constant time. [/*] [*] Let us define a variant of $\textbf{P}_{angel}$ called $\textbf{P}_{bad-angel}$ with a constraint that there should exists a polynomial time algorithm that can [b]compute[/b] the angel string for any length $n \in \mathbb{N}$. In other words, there is a poly-time algorithm $A$ such that $\alpha_n = A(n)$. \\Is $\textbf{P} =\textbf{P}_{bad-angel}$? Is $\textbf{NP}=\textbf{P}_{bad-angel}$? Justify. [/*] [*] Let the language $L \in$ $\textbf{P}_{angel}$. Show that there exists a sparse set $S_L$ and a deterministic polynomial time TM $M$ with oracle access to $S_L$ that can decide the language $L$. [/*]