Re: PSPACE closed under union

hbdere <hbdere@xxxxxxx> wrote:
On Apr 12, 4:43 pm, "cooldavid" <vmvicto...@xxxxxxxxx> wrote:
So yeah, the answer should be short.
Ok, the single word is "dovetailing":
http://en.wikipedia.org/wiki/Dovetailing_%28computer_science%29

Since the languages are in PSPACE, there exists a polynomial space
decider for them; not a polynomial space recognizer. So dovetailing
should not be necessary, because the first machine is guaranteed to
terminate anyway.

--
Chris Smith
.