Question

Let BPL be the collection of languages that are decided by probabilistic log space Turing machines with error probability$\frac{1}{3}$. Prove that$\mathbf{BPL}\subseteq \mathbf{P}$

Short answer

The above problem is solved using probabilistic log space TM (Turing Machine)

Step-by-step solution

 Understanding the given problem

Suppose$BPL$be the collection of languages which are judged by probabilistic log space TM (Turing Machine) with an error probability of$\frac{1}{3}$. Now, suppose L be a BPL language and the machine M is required as the definition of BPL says.

 Defining the way to solve the problem

On input x of length n, suppose the number of $M\left(\mathrm{...}x\right)$configuration of is defined as C. A $CxC$matrix is constructed in such a way that $P[c_1,c_2]=\frac{1}{3}$if $c_2$is reachable from $c_1$in a single step, and$P[c_1,c_2]=0$ otherwise.

For all t,$P^{\text{'}}[c_1,c_2]$is defined as the probability of approaching configuration$c_2$ from configuration $c_1$in t number of steps. Here, p is defined as the matrix obtained by multiplying p with itself t times.

Following the procedure to complete the solution

The accepting probability of $M\left(\mathrm{...}x\right)$can be computed by computing all powers oftill the $M\left(\mathrm{...}x\right)$running time of and decide if $x\in L$.

The exact calculation can be performed at this time: each probability is an integer multiple of${\frac{1}{3}}^{p\left(n\right)}$ . So, the polynomial number of digits can be used to represent it.

Hence, it can be said that $BPL\subseteq P$.