Question

Prove that $\mathbf{TQBF}\mathbf{\notin }\mathbf{SPACE}\left(n^{1/3}\right)$

Short answer

Using the space hierarchy theorem, we are going to solve the above problem.

Step-by-step solution

Defining the space hierarchy theorem

We can define the space hierarchy theorem as “if g is a space-constructible $\mathbf{(}{\mathbf{1}}^{\mathbf{n}}\mathbf{\to }{\mathbf{1}}^{\mathbf{g}\left(n\right)}$can be computed in space $\mathbf{O}\left(g\left(n\right)\right)$,$\mathbf{f}\left(n\right)\mathbf{=}\mathbf{O}\left(g\left(n\right)\right)$ then $\mathbf{SPACE}\left(f\left(n\right)\right)\mathbf{\varnothing }\mathbf{SPACE}\left(g\left(n\right)\right)$,

Thus, it is known from space hierarchy theorem that there exists a language L , which is solvable in linear space but not in sub-linear space.

Arriving at the contraction to prove the answer

‘L’ can be reduced TQBF in log space since, TQBF is space-complete. So, if$\mathbf{TQBF}\mathbf{\notin }\mathbf{SPACE}\left(n^{1/3}\right)$ then role="math" localid="1657785362677" $\mathbf{L}\mathbf{\notin }\mathbf{SPACE}\mathbf{(}{\left(n^c\right)}^{\mathbf{1}\mathbf{/}\mathbf{3}}\mathbf{+}\mathbf{log}\left(n\right)\mathbf{)}$,

Now, suppose if 0.33<1 / c , then there exists a contradiction

Hence, it can be said that$\mathit{T}\mathit{Q}\mathit{B}\mathit{F}\mathbf{\notin }\mathbf{SPACE}\left(n^{1/3}\right)$