Probability of randomly designated subsets cover the universe
Frage
Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.
Is there a polynomial time algorithm that computes:
$$\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right]$$
Or is there any equivalent famous problem?
Keine korrekte Lösung
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange