# Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

I want to show that $$A_\mathrm{LBA}$$ is PSPACE-Compelte.

Say we proved it is in PSPACE. Now for PSPACE-HARD:

I had an idea, which was very similar to some solution i found on the web- say we have a TM M which decides some language A in PSPACE. Then given an x in A we can simulate M on x to determine the number of steps M makes.

Suppose the above simulation is defined as another TM M' and k steps are needed for M to run x.

Build a TM M'' which simulates M on "x, $$space^{\mathrm{k}}$$" - the word x concatenated with k spaces. return (M'', "x, $$space^{\mathrm{k}}$$")

What i don't understand - the input is only x and its length is |x| so how do we know that simulating M on x is poly-time(x) ? we don't know the size of the description of M, which must be fed to the single-tape LBA M''.

How come all the solutions i've encountered don't even mention that the size of the description of M might not be poly-time(x) ? then we have that the mere writing of M on M''s tape might be more than poly-time(x). (?)

No relation is given between |x| and |M| (the decider for A) because the input is only the word x...

As I understand, you are asking two questions. Let me address them separately:

1. You don't. Your assumption on $$M$$ did not require anything more than $$L(M) = A$$, which is too weak for such a proof. You need to use $$A \in \textbf{PSPACE}$$ and require the existence of a polynomial $$p: \mathbb{N} \to \mathbb{N}$$ such that $$M$$ uses at most space $$p(n)$$ for any input of length $$n$$.

Incidentally, you also need this to know what $$k$$ should be. In your proof, you give no explicit way of computing $$k$$ other than simulating $$M'$$, but you do not state why this could ever be done in poly-time. (In fact, this could only ever work for arbitrary $$M$$ if $$\textbf{P} = \textbf{PSPACE}$$.)

2. The description of $$M$$ remains constant as the length of the input $$x$$ increases, so it is negligible, asymptotically speaking.

## The real issue

It appears your approach is based on fixing $$A$$ and $$x$$ and then constructing an LBA $$M''$$ to simulate $$M$$ on $$x$$. This is not how reductions work. $$A$$ and $$M$$ should be fixed, but you need to keep $$x$$ arbitrary, otherwise the proof is quite incorrect (since the result of running $$M$$ on $$x$$ could be simply hardcoded into a TM which produces the result immediately upon reading $$x$$ as input; this proves absolutely nothing).

• Yes, i meant that A and M are fixed. So how can the proof be completed ? how can i find the number of spaces to pad with ? – caffein Dec 30 '18 at 0:15
• Is saying "return <M>" means O(1) time or do we have to write the full description of M in order to return it which might be very long ? – caffein Dec 30 '18 at 0:17
• How can i find k in poly-time ? – caffein Dec 30 '18 at 0:34
• @caffein You do not need to find the precise value of $k$; you can just compute $p(|x|)$ and use it instead (by assumption it suffices for the simulation performed by $M''$). Ad your other question: computing $\langle M \rangle$ takes constant, that is, $O(1)$ time (and space) wrt to $x$, regardless of how long the description is. – dkaeae Dec 30 '18 at 1:06
• By computing p(|x|) you mean to write it as part of the machine description ? Not to actually compute it right ? To feed the description "compute p(|x|)" into the machine yes ? – caffein Dec 30 '18 at 1:22