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...
올바른 솔루션이 없습니다