4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$. I will show that such an exact solution would provide a polynomial time algorithm for set-cover.

Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-cover. Let $m = |S|$.

Let $$ \Gamma = \left\{ K \in \mathscr{P}(S) : U =\bigcup_{X \in K} X \right\} $$

For each $h \in \mathbb{N}$ let:

$$ \nu_h = |\{K \in \Gamma : |K|=h\}| $$

Observe that our instance of set-cover is satisfiable if and only if $\nu_k \neq 0$.

Now, let $T$ be a set, constructed as in the problem statement. $T$ covers $U$ if and only if $T \in \Gamma$. Therefore:

$$ \mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right] = \mathbb{Pr}[T \in \Gamma] = \sum_{X\in\Gamma}p^{|X|}(1-p)^{m-|X|} = \sum_{h=0}^m \nu_h p^h(1-p)^{m-h} $$

The rightmost expression is a polynomial over the ring $\mathbb{Q}[p]$, which means that its coefficients can be found by computing its value at $m-1$ points and applying an algorithm such as the finite differences method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.