Define pad as in Problem 9.13

1. Prove that for every A and natural number k, $\mathrm{A}\in \mathrm{P}$ if$\mathrm{pad}(\mathrm{A},{\mathrm{n}}^{\mathrm{k}})\in \mathrm{P}$
2. Prove that$\mathrm{P}\ne \mathrm{SPACE}\left(\mathrm{n}\right)$

A language is said to be Turing Recognizable if and only if there exists any Turing Machine (TM) which recognizes it i.e., TM halts and accepts strings that belong to the language and will reject or not halt on the input strings that don’t belong to the language .

For any function$\mathrm{f}:\mathrm{N}\to \mathrm{N}$and language A,$\mathrm{pad}(\mathrm{A},\mathrm{f})$is defined as:

$\mathrm{pad}(\mathrm{A},\mathrm{f})=\left\{\mathrm{pad}\right(\mathrm{s},\mathrm{f}\left(\mathrm{m}\right)\left)\right|$where$\mathrm{s}\in \mathrm{A}$and ‘m’ is the length of ‘s’ }.

Let A be any language and$k\in N$ .

$pad\left(A,n^k\right)\in P$only if$A\in P$, because we can determine whether $w\in pad\left(A,n^k\right)$by writing ‘w’ as ‘s#’ where, ‘s’ does not contain the ‘#’ symbol. Then, it is tested whether $\left|w\right|=|s{|}^k$and then it is tested that whether $s\in A$.

The second test runs in time $poly\left(\left|s\right|\right)$because$\left|s\right|⩽\left|w\right|$ , since the test runs in time$poly\left(\left|w\right|\right)$ , it is polynomial in time.

It can be determined whetherby padding ‘w’ with ‘#’ symbols until it has length$|w{|}^k$and then, test whether the result is in$pad\left(A,n^k\right)$i.e., $A\in P$only if$pad\left(A,n^k\right)\in P$.

Hence, it can be said that $A\in P$holds only if $pad\left(A,n^k\right)\in P$ .