Recent content by Xavier Labouze

No it doesn't work either : by removing all ##2^{|C_1|}## subsets of ##A_1##, it is as if all the ##C_1## elements form a proper subset in another subset than ##A_1## which is not sure...

@Office_Shredder is right. The algorithm does not work, it misses a lot of subsets of ##A_1##. An idea may be is to count all subsets only included in ##P(A_1)## , i.e. ##P(C_1) X [P(D_1)- \emptyset]## (they are ##2^{|A_1|}-2^{|C_1|}##) and to continue... that is to say, replace ##2^{|D_1|}##...

It looks good - but it doesn't work (see the comment below...) .

No - With ##k## bounded by a polynom in ##n##

A polytime algorithm in ##n=|A|## (Nice quote BTW)

Thank you, my question was written wrong - my first question on this forum, my bad.

The question is : is it the best (the fatest) way to compute theses unions ? How to prove it ?

It seems I can't change the question any more...

I must have written the question wrong. I am a teacher not a student and I wonder if counting the cardinality of unions of powersets can be computed in polynomial time (or is it #NP-Complete ?). If you have the answer please give it to me. I should certainly change the question in this way...

Right, ##|P(A_1) \cup P(A_2)|=|P(A_1)|+|P(A_2)|-|P(A_1 \cap A_2)|## but I don't see how to continue...

Tks. No it is not a homework. I really wonder if it exists an algorithm running in polynomial time in ##n## (the cardinality of ##A##) - About your comment : ##P(A) \cap P(B) = P(A \cap B)## but ##\overline{P(A)} \ne P(\overline{A})## so how to deal with it?

Mentor note: In this thread I (Mark44) have edited "cardinal" to "cardinality." In English, we talk about the "cardinality of a set," not the "cardinal of the set." Given A a set of n elements - note |A| its cardinal and P(A) its powerset. Let A1, A2... Ak, be k subsets (not empty) of A. What...

Interested in Computer Science, Art and Diplomacy...