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...

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

1 Answer 1


Savitch's theorem shows that PSPACE=NPSPACE, which immediately implies that ALBA is in PSPACE.

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|)})$.

  • $\begingroup$ thanks. I dont still understand how the reduction works. We have TM L in space p(n). Then TM L′ which accepts (x,y) = x is the the string which is input to M? (linear bounded automata) and y is what? Can you give me example, how these two Turing machines work together? Also, what is 0p(|x|)? p is some function polynomal, x is size of input x and 0 is what? $\endgroup$
    – Arthemoon
    Dec 2, 2020 at 22:51
  • $\begingroup$ Here $0$ is the letter zero and $0^n$ is the letter zero repeated $n$ times. $\endgroup$ Dec 3, 2020 at 6:41
  • $\begingroup$ and what is "y"? how the second machine works? it accepts x and y and do what with it? and why the second machine has the second argument Oto(p(x)? $\endgroup$
    – Arthemoon
    Dec 3, 2020 at 10:42
  • $\begingroup$ Here $y$ is a dummy input, whose sole purpose is to pad the input to make it large enough. $\endgroup$ Dec 3, 2020 at 10:56
  • $\begingroup$ I’m not including all the details since it’s an exercise. $\endgroup$ Dec 3, 2020 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.