Re: PSPACE closed under union

cooldavid <vmvictorvm@xxxxxxxxx> wrote:
So yeah, the answer should be short.

I'm thinking something like, Let A1 be a TM/algorithm that solve L1 in
polyspace and let A2 be be a TM/algorithm that solved L2 in polyspace.
Now the algorithm/TM below (A3) will solved L1 U L2 in polyspace.

A3 = "On input x"
"don't know what to do here".

Do you understand why this is true? If you can run A1 in polynomial
space; and you can run A2 in polynomial space, then of course you can
run each machine in turn on the same input, and it will still take
polynomial space. Depending on how pedantic you want to be, you could
introduce some details about how you keep a copy of the input while the
first machine is running.

--
Chris Smith
.