Recall that normally we assume that numbers are represented as string using the binary basis.

That is$,$ a number n is represented by the sequence x$0,$ x$1,...,$ xlogn such that n $=$

logn

i$=0$

xi$2$

i

$,$

where for each i in $[0..$logn$]$ xi in $\{0,1\}.$ However, we could have used other encoding

schemes. If n in N and b $>=2,$ then the representation of n in base b$,$ denoted by $[$x$]$b is

obtained as follows: first represent n as a sequence of digits in $\{0,...,$b $1\},$ and then

replace each digit d in $[0..$b$1]$ by its binary representation. The unary representation of n$,$

denoted by $[$n$]1$ is the string $1$n

$($i$.$e$.,$ a sequence of n ones$).$

$($a$)$ Show that choosing a different base of representation will make no difference to the

class P$.$ That is$,$ show that for every subset S of the natural numbers, if we define

L

b

S $=\{[$n$]$b : n in S$\}$ then for every b $>=2,$ L

b

S in P $$ L

$2$

S in P$.$