Question

Show that $\mathbf{P}$is closed under the star operation. (Hint: Use dynamic programming. On input $\mathbf{y}\mathbf{=}{\mathbf{y}}_{\mathbf{1}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathbf{y}}_{\mathbf{n}}\mathbf{for}{\mathbf{y}}_{\mathbf{i}}\mathbf{\in }\mathbf{\Sigma }$, build a table indicating for each $\mathbf{i}\mathbf{\le }\mathbf{j}$ whether the substring ${\mathbf{y}}_{\mathbf{i}}\mathbf{·}\mathbf{·}\mathbf{·}{\mathbf{y}}_{\mathbf{j}}\mathbf{\in }\mathbf{A}\mathbf{\ast }\mathbf{for}\mathbf{any}\mathbf{A}\mathbf{\in }\mathbf{P}\mathbf{.}\mathbf{)}$

Short answer

The solution is,

$\mathrm{p}=\underset{\mathrm{k}}{\cup }\mathrm{TIME}\left({\mathrm{n}}^{\mathrm{k}}\right)$

Step-by-step solution

To Indication of P

By using dynamic programming system we can apply input and build a table which is indicate p is closed under the star operation.

To Classification of Polynomial time

P seems to be a classification representing languages which can be deduced within polynomial time that used a deterministic solitary tape Turing computer. That is correct

$\mathrm{p}=\underset{\mathrm{k}}{\cup }\mathrm{TIME}\left({\mathrm{n}}^{\mathrm{k}}\right)$