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.