Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ .
The basic approach probably would be to use the classic inclusion-exclusion principle $\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|$ , where $A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$ .
However, inclusion-exclusion feels like it's terribly inefficient - after all, we need to sum over $\displaystyle\sum_{i=1}^n\binom{n}{i} = 2^n-1$ possible sets.
While I guess that there's no algorithm with polynomial complexity for this problem, I'm curious about alternatives that are more efficient (i.e. have polynomial run time in most cases), or are simply largely different.
I'd be thankful if you could name alternative algorithms or optimizations to inclusion-exclusion.
The particular problem I'm trying to write an algorithm for is unsatisfiability in Propositional logic for formulas in CNF. I.e. we have a finite set of atomic formulas $\{p_1,...,p_m\}$. Over these atomic formulas, the clauses of the CNF of the formula are built after these rules:
For ever atomic formula $p$, there may either appear $p$, $\lnot p$ or none of the two in the clause.
As the whole problem was either $NP$ or $co-NP$, there most likely isn't a polynomial algorithm, but I am struggling to just make it anyhow just a little bit more efficient than inclusion-exclusion (besides using ideas that have little to do with the algorithm itself like pure-literals or pure-clauses).
Yes, each set itself is discrete with each element in the set being specified. One example would be $\{ \{\bar A, B \},\{B,C \},\{ A,B \} \}$. However, to fit the example, the initially given inclusion-exclusion algorithm would need to be modified.
This is the case as every clause in the CNF is a representative for a bigger clause, e.g. in the above example $\{\bar A, B \}$ stands for
$
\{\bar A, B ,C \}
\{\bar A, B ,\bar C \}
$
and $\{B,C \}$ stands for
$
\{B,C, A \}
\{B,C ,\bar A \}
$
You get the actual set the representative represents by the following algorithm:
Be $M$ a set of the clause, and $S$ our output set. Add $M$ to $S$. Now repeat as long as possible:
Find an atomic formula $A$ so that $A\notin K$ and $\bar A \notin K$ for some $K\in S$.
Remove $K$ from $S$.
Add $K\cup \{A\}$ and $K\cup \{\bar A\}$ to $S$.
Finally, delete all sets in $S$ where $A,\bar A \in S$ for some $A$ and return $S$.
(An atomic formula in this case is simply any letter somewhere in $M$ without the bar (i.e. $A$ for $\bar A$))
This version of the algorithm however is at this point pretty dumb. You can improve it by not explicitly generating the actual sets and calculate it with the representants and applying some arithmetic instead.
It goes like this:
Let $A_1,...,A_n$ be our atomic formulas that appear in a set of clauses $\mathcal{K}$. For every $K\in\mathcal{K}$ you can calculate how many sets $K$ actually represents by counting the elements of $K$, let's name it $c$, and calculate $2^{n-c}$.
So, we calculate the sum all the way above, i.e. $$\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|\text{ , where }A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$$
just that we calculate $|A_I|$ not by $\big|\,\,\displaystyle\bigcap_{i\in I}^n S_i\big|$, but by calculating how many sets $\,\,\displaystyle\bigcup_{i\in I}^n S_i$ represents (with special case $|A_I|=0$, if $A_I$ contains $A$ and $\bar A$ for some atomic formula).
