# Show linear bounded automata accepting w is PSPACE-complete

ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w}


Show that ALBA is PSPACE-complete.

How I would try to solve it...

1. We need to prove ALBA belongs to PSPACE. So I would construct TM A which accepts <M;w>. Simulate M till qng^n steps or when it halts. If it halts: Accept <M,w> if M accepts w, otherwise reject. How would be space complexity? I would say it will need n (=size of the tape) so space complexity should be O(n) and then ALBA belongs to PSPACE. Is it correct?

2. We need to do reduction from TQBH to ALBA to prove that ALBA is NP hard, but I have no idea how to do it. How should this reduction be done? TQBF must be 1 if ALBA accepts w i guess, but dont know how to show the proof...

• In part 2, don't try a reduction from TQBF. Use the definition of PSPACE instead. Dec 2, 2020 at 12:54
• @Yuval Filmus What do you mean "definition of PSPACE"? Would you please give me a little bit more information? Dec 2, 2020 at 13:03
• Given a Turing machine $T$ using space $p(n)$ (for some polynomial $p$) and an input $x$, determine whether $T$ accepts $x$. Dec 2, 2020 at 14:15

In the other direction, suppose that $$L$$ is a language in PSPACE. Thus $$L$$ is accepted by some machine that uses space $$p(n)$$. We can construct another machine $$L'$$ which accepts an input $$(x,y)$$, erases $$y$$, and simulates $$L$$ on $$x$$. We can reduce $$L$$ to ALBA by mapping $$L$$ to $$L'$$ and $$x$$ to $$(x,0^{p(|x|)})$$.
• Here $0$ is the letter zero and $0^n$ is the letter zero repeated $n$ times. Dec 3, 2020 at 6:41
• Here $y$ is a dummy input, whose sole purpose is to pad the input to make it large enough. Dec 3, 2020 at 10:56