(a) Consider the function $f:\{0,1\}^{*} ightarrow\{0,1\}^{*}$ which converts binary to unary, i.e., if $x$ is a binary representation of an integer $n$, then $f(x)=1^{n}$ (so for example $f(101)=11111, f(01)=1$, and $f (000)=\varepsilon$ ). Is it possible to compute $f$ in polynomial time? (b) What is wrong with the following argument? The language $L=0^{*} 1^{*}$ is regular, so it is in $\operatorname{TIME) (n)$ and thus in $\mathrm{P}$. Now for any language $R \in \mathrm{P}$, there is a reduction $R \leq_{P] L$, so $R Vin \operatorname{TIME}(n) $ as well. Therefore any problem solvable in polynomial time is solvable in linear time. (c) Let $P CP_{\text {short }}$ be a variant of the Post Correspondence Problem where we require that if there are $n$ types of dominoes, a match can have length at most $n^{10}$. Show that $P C P_{\text {short }} \in \mathrm{ND}$. (d) Let $N P_{\text {log }}$ be a modified version of NP where the certificate for an input $x$ is required to be of length $0(\log |x| $. Argue that $\mathrm{P}=\mathrm{NP}_{\log }$. CS.VS. 1156