Question

Consider the following function $\mathbf{pad}\mathbf{:}\mathbf{\sum }\mathbf{*}\mathbf{\times }\mathbf{{\rm N}}\mathbf{\to }\mathbf{\sum }\mathbf{*}{\mathbf{\#}}^{\mathbf{*}}$that is defined as follows. Let PAD (s, l) = s#³, where j = max (0,l - m) and mis the length of s. Thus, pad (s, l)simply adds enough copies of the new symbol # to the end of s so that the length of the result is at least l. For any language A and function $\mathit{f}\mathbf{:}\mathit{N}\mathbf{\to }\mathit{N}$, define the language pad(A, f) as$\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}\mathbf{f}\mathbf{)}\mathbf{=}\mathbf{\{}\mathbf{pad}\mathbf{(}\mathbf{s}\mathbf{,}\mathbf{f}\mathbf{(}\mathbf{m}\mathbf{\left)}\mathbf{\right)}\mathbf{|}$ where $\mathbf{s}\mathbf{\in }\mathbf{A}$and ‘m’ is the length of ‘s’ }. Prove that if $\mathbf{A}\mathbf{\in }\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{6}}\mathbf{\right)}$, then $\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}{\mathbf{n}}^{\mathbf{2}}\mathbf{)}\mathbf{\in }\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{3}}\mathbf{\right)}$.

Short answer

Using Turing machine M, we are going to find the solution for the above problem.

Step-by-step solution

Understanding the ‘given’ in the problem

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

$\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}\mathbf{f}\mathbf{)}\mathbf{=}\mathbf{\{}\mathbf{pad}\mathbf{(}\mathbf{s}\mathbf{,}\mathbf{f}\mathbf{(}\mathbf{m}\mathbf{\left)}\mathbf{\right)}\mathbf{|}$whererole="math" localid="1657786465759" $\mathbf{s}\mathbf{\in }\mathbf{A}\mathbf{}$and ‘m’ is the length of ‘s’ }.

Suppose M be a machine that decide A in time ${\mathbf{n}}^{\mathbf{6}}$only if$\mathbf{A}\mathbf{\in }\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{6}}\mathbf{\right)}$

Solving the problem by considering the machine M

Now, consider machine M for$\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}{\mathbf{n}}^{\mathbf{2}}\mathbf{)}$ that on input x, check if x is of the format $\mathbf{pad}\mathbf{(}\mathbf{w}\mathbf{,}\mathbf{|}\mathbf{w}{\mathbf{|}}^{\mathbf{2}}\mathbf{)}$for some string $\mathbf{w}\mathbf{\in }\mathbf{\sum }\mathbf{*}$.

Input x will be rejected if it will not be matched. Or else simulate M on w.

Let$\mathbf{O}\mathbf{\left(}\mathbf{\right|}{\mathbf{x}}^{\mathbf{3}}\mathbf{\left|}\mathbf{\right)}\mathbf{+}\mathbf{O}\mathbf{\left(}\mathbf{\right|}\mathbf{w}{\mathbf{|}}^{\mathbf{6}}\mathbf{)}\mathbf{=}\mathbf{O}\mathbf{(}\mathbf{\left|}{\mathbf{x}}^{\mathbf{3}}\mathbf{\right)}$ be the running time of machine M

Hence, we can say that$\mathbf{pad}\mathbf{(}\mathbf{A}\mathbf{,}{\mathbf{n}}^{\mathbf{2}}\mathbf{)}\mathbf{\in }\mathbf{TIME}\mathbf{\left(}{\mathbf{n}}^{\mathbf{3}}\mathbf{\right)}$