Why is clutter problem intractable for large sample sizes? Suppose we have a set of points $\mathbf{y} = \{y_1, y_2, \ldots, y_N \}$. 
Each point $y_i$ is generated using distribution
$$
p(y_i| x) = \frac12 \mathcal{N}(x, 1) + \frac12 \mathcal{N}(0, 10).
$$
To obtain posterior for $x$ we write
$$
p(x| \mathbf{y}) \propto p(\mathbf{y}| x) p(x) = p(x) \prod_{i = 1}^N p(y_i | x). 
$$
According to Minka's paper on Expectation Propagation we need $2^N$ calculations to obtain posterior $p(x| \mathbf{y})$ and, so, problem becomes intractable for large sample sizes $N$. However, I can't figure out why do we need such amount of calculations in this case, because for single $y_i$ likelihood has the form 
$$
p(y_i| x) = \frac{1}{2 \sqrt{2 \pi}} \left( \exp \left\{-\frac12 (y_i - x)^2\right\} + \frac{1}{\sqrt{10}} \exp \left\{-\frac1{20} y_i^2\right\} \right).
$$
Using this formula we obtain posterior by simple multiplication of $p(y_i| x)$, so we need only $N$ operations, and, so we can solve this problem for large sample sizes exactly. 
I make numerical experiment to compare do I really obtain the same posterior in case I calculate each term separately and in case I use product of densities for each $y_i$. Posteriors are same. See 

Where am I wrong? Can anyone make it clear to me why do we need $2^N$ operations to calculate posterior for given $x$ and sample $\mathbf{y}$?
 A: You are right that the paper is saying the wrong thing.  You certainly can evaluate the posterior distribution of $x$ at a known location using $O(n)$ operations.  The problem is when you want to compute moments of the posterior.  To compute the posterior mean of $x$ exactly, you would need $2^N$ operations.  This is the problem that the paper is trying to solve.
A: You missed the point that the distribution is a mixture of Gaussians:
each sample $y_i$ is either distributed as per $p(y_i | x)$ with probability $1-w$ and as $p_c(y)$ (clutter distribution for $y$, independent of $x$) with probability $w$. 
Let $c_i$ be the indicator variable indicating that sample $i$ was draw from 
the clutter distribution; thus, if it's $0$ it indicates that the sample was drawn from $p(y|x)$.  Obviously, if the sample was drawn from the clutter distribution it's value is irrelevant for the estimation of $x$.
It's the presence of the $2^N$ possible joint states for these indicator variables that causes the problem.
