0

I have an equation the uses the inclusion-exclusion principle to calculate the probabilities of correlated events by removing the duplicate counting of intersections.

Now I want to know the complexity of this equation: What is the cost of computing the inclusion-exclusion principle in relation to the number of elements? is it exponential?

flag
4 
 Could you please be more detailed. In particular, what does 'computing the inclusion-exclusion principle' mean? – quid Jul 27 2011 at 1:44
2 
 There are a priori exponentially many subsets to sum/difference over. But there may be ways to expedite the computation. If you don't find the answer you're looking for here on MO, you may have better luck on some of the more CS-themed StackExchange sites. They are, in no particular order, stackoverflow.com, superuser.com, stackexchange.com, and cstheory.stackexchange.com. But please note that I am not active on any of those fora, and in particular don't know which would be the best fit for your question. It's likely that there are better sites I am unaware of. – Theo Johnson-Freyd Jul 27 2011 at 2:18
mathoverflow.net/questions/38278/… but my question was about enumeration, not counting :-) – Nathann Cohen Jul 27 2011 at 8:55

closed as not a real question by Mark Sapir, Andres Caicedo, Emil Jeřábek, Willie Wong, Qiaochu Yuan Jul 27 2011 at 17:20

Browse other questions tagged or ask your own question.