$1.$ Recall that for a language Lsube$\{0,1{\}}^{**}$ and $n0,L=n=L\{0,1{\}}^n.$

$($a$)$ A language $L$ is lonely if for all $n0,|L_{?}=n|=1.$ In other words, $L$ is lonely if it has

exactly one string at length $n.$ Let

LONELY $=\{Lsube\{0,1{\}}^{**}|Lis$ lonely $\}.$

Prove that LONELY sube$\frac{P}{n}.$

$($b$)$ A language $L$ is sparse if there is a polynomial $p(n)$ such that for all $n0,$

$|L_{?}=n|p(n).$

Let

SPARSE $=\{Lsube\{0,1{\}}^{**}|Lis$ sparse $\}.$

Prove that SPARSEsubeP$/$ poly.

$2.$ Prove P$/$poly $=BP$P$/$ poly.