Re: PSPACE closed under union

On Thu, 12 Apr 2007 16:43:59 +0200, cooldavid <vmvictorvm@xxxxxxxxx> wrote:

On Apr 12, 1:52 am, "hbdere" <hbd...@xxxxxxx> wrote:
On Apr 11, 9:33 pm, "cooldavid" <vmvicto...@xxxxxxxxx> wrote:> I know that we have to:
> Let L1 in PSPACE and L2 in PSPACE.
> Want to show: L1 U L2 in PSPACE
> How to show that?

Maybe you first tell us where your problem is, because unless I am
greatly mistaken an informal proof is just one word long, and telling
you that word would spoil the idea of homework assignments, right?

This is not a homework assignment, but I'm preparing for my final
exam.

The problem is asking us to prove the PSPACE closure. If I know how
to do it with UNION, then I may be able to understand the other one by
myself.

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

Well, what does "x belong to (L1 UNION L2)" mean ?

Can you rephrase "x belongs to (L1 U L2)" in a equivalence sentence without using union ? [this is basic set theory]
Using this new formulation, can you use A1 and/or A2 to decide some of the belonging in it ?
Can you then combine everything (in a PSPACE way) to decide the whole thing ?

--
Hypocoristiquement,
Jym.
.