Re: PSPACE closed under union

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

If you understand that concept, you can immediately prove the closure
under union or intersection. Of course, you need to know that the sum
of two polynoms is itself a polynom.

If you want to do the entire proof, you need to describe how the
dovetailing can be done. This is easy if multiple tapes can be used.

.

Relevant Pages

  • Re: discrete set
    ... Union of sets may not be discrete. ... What do you mean by "a sum of sets"? ... but thought "intersection is discrete". ...
    (sci.math)
  • Re: sum of zetas
    ... idea of elementary symmetrical polynoms and the ... elements P(if you have the sum of the crossproducts) ... of powers (plus the related lower-exponent items, ... have the same modulus base polynom-of 2 - and we cannot ...
    (sci.math)