Re: PSPACE closed under union

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


.

Relevant Pages

  • Re: PSPACE closed under union
    ... > Let L1 in PSPACE and L2 in PSPACE. ... polyspace and let A2 be be a TM/algorithm that solved L2 in polyspace. ... Can you rephrase "x belongs to " in a equivalence sentence without using union? ...
    (comp.theory)
  • Re: PSPACE closed under union
    ... Let L1 in PSPACE and L2 in PSPACE. ... greatly mistaken an informal proof is just one word long, ... you that word would spoil the idea of homework assignments, ...
    (comp.theory)