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|}##...
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...
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...