Question

Problem 8.13 showedthat ${\mathbf{A}}_{\mathrm{LBA}}$is $\mathbf{PSPACE}\mathbf{-}$complete.

a) Do we know whether${\mathbf{A}}_{\mathrm{LBA}}\mathbf{\in }\mathit{N}\mathit{L}$?Explain your answer.

b) Do we know whether${\mathbf{A}}_{\mathrm{LBA}}\mathbf{\in }\mathit{P}$ ?Explain your answer.

Short answer

a) Using Savitch’s theorem which states that$PSPACE=NSPACE$ and also by using the space hierarchy theorem, it can solve the above problem.

b) The above problem can be solved by using the corollary of Savitch’s theorem, which states that $PSPACE=NSPACE$i.e., the deterministic space complexity and non-deterministic polynomial space complexity are same basically.

Step-by-step solution

Understanding the PSPACE 

$PSPACE$is basically the class of the language. Whether the language belongs to deterministic finite automata or non-deterministic finite automata is decided based on the polynomial time Turing Machine.

If a language belongs to$PSPACE$ it is said to be $PSPACE$-complete.

Proving that.ALBA∈NL

a).

But it is given that$NP\in NPSPACE$ is -$PSPACE$complete.

Using space hierarchy theorem, we can prove that.$A_{LBA}\in NL$

We know that$\mathbf{PSPACE}\mathbf{=}\mathbf{NSPACE}$ (From the corollary of the Savitch’s theorem) which implies that the deterministic space complexity and non-deterministic polynomial space complexity are same basically.

Space complexity of $PSPACE$ is$O\left(\log n\right)$and space complexity of$NSPACE$is$O\left(n^k\right)$for each and every value of$k_i$Therefore, it implies that the language is basically accepted by $NSPACE$but not by.$NL$

But from the space hierarchy theorem, it is known that the language is accepted both by $PSPACE$ and also $NL$.

So,$NL\in PSPACE$ and it is given that$A_{LBA}\in PSPACE$

Thus, it can be said that $A_{LBA}\in NL$