Test if there are two subsets which cover a set

Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?

There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to
$$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$
Indeed, if $\chi_U$ is the indicator vector of $U$ then
$$ \chi'_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$
The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\{0,1\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h_U = g_{\overline{U}}$. The FFT algorithm uses the basic operation $h_{U \cup \{i\}} = h_U \lor h_{U \cup \{i\}}$. This makes it clear why $\bigvee_U f_U g_U = \bigvee_U f_U h_{\overline{U}}$ is what we want.

StackExchange Computer Science Q#10250, answer score: 3