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


1 Answer 1


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

  • $\begingroup$ 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 ? $\endgroup$
    – caffein
    Commented Dec 30, 2018 at 0:15
  • $\begingroup$ 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 ? $\endgroup$
    – caffein
    Commented Dec 30, 2018 at 0:17
  • $\begingroup$ How can i find k in poly-time ? $\endgroup$
    – caffein
    Commented Dec 30, 2018 at 0:34
  • $\begingroup$ @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. $\endgroup$
    – dkaeae
    Commented Dec 30, 2018 at 1:06
  • $\begingroup$ 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 ? $\endgroup$
    – caffein
    Commented Dec 30, 2018 at 1:22

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.