Question

Prove that if $\mathbf{A}\mathbf{\in }\mathbf{P}$, then$\mathbf{}{\mathbf{P}}^{\mathbf{A}}\mathbf{=}\mathbf{P}$

Short answer

Using the polynomial Turing Machine, we can prove the above statement.

Step-by-step solution

Understanding the given elements in the problem

Given:$\mathbf{A}\mathbf{\in }\mathbf{P}$i.e., Language A belongs to the polynomial Turing Machine P.

To Prove:$\mathbf{}{\mathbf{P}}^{\mathbf{A}}\mathbf{=}\mathbf{P}$ i.e. $\mathbf{}{\mathbf{P}}^{\mathbf{A}}$, which is the class of the language that can be decidable with the polynomial Turing Machine which uses language A.

Construction of the proof

Construction:

Whether the stringw is the member of Aor not is checked by Language A.

Let, string wcontains the value $\left\{a^n{b}^n\right\}$and user gave $\left\{\mathrm{aabb}\right\}$which is accepted byA.

If the string$\left\{\mathrm{aabbb}\right\}$ is specified then it is not expected by A. Now, let us check this for the poly-time Turing Machine:

Suppose Nis the poly-time Turing Machine

• The computation path of N is found which leads to the acceptance of the polynomial.
• If the String is not accepted ‘no’ query will execute, if accepted ‘yes’ query will execute.
• Whether all the strings are accepted or not is checked by Machine N

So, here the computation is done for all the strings and hence, it can be proved that${\mathbf{P}}^{\mathbf{A}}\mathbf{=}\mathbf{P}$