質問

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

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top