1
$\begingroup$ 
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...

Improve this question
$\endgroup$
3
  • $\begingroup$ In part 2, don't try a reduction from TQBF. Use the definition of PSPACE instead. $\endgroup$ – Yuval Filmus Dec 2 '20 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 '20 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$ – Yuval Filmus Dec 2 '20 at 14:15
1
$\begingroup$

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

Improve this answer
$\endgroup$
19
  • $\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 '20 at 22:51
  • $\begingroup$ Here $0$ is the letter zero and $0^n$ is the letter zero repeated $n$ times. $\endgroup$ – Yuval Filmus Dec 3 '20 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 '20 at 10:42
  • $\begingroup$ Here $y$ is a dummy input, whose sole purpose is to pad the input to make it large enough. $\endgroup$ – Yuval Filmus Dec 3 '20 at 10:56
  • $\begingroup$ I’m not including all the details since it’s an exercise. $\endgroup$ – Yuval Filmus Dec 3 '20 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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