Herewith I submit what may or may not be considered a simpler version of this question.

The question is whether it is provable that there is no efficient deterministic numerical method for a particular task that will be done by Monte Carlo below.

It was proposed that on average a motorist takes longer to leave a parking space when someone is waiting for that space than when that is not the case. To test this, data were collected. The number of seconds taken by 20 persons leaving a parking space with no one waiting and by 20 others with someone waiting was recorded. The average time taken by those with someone waiting exceeded the average of the other 20 by about $9.8$ seconds. As one would expect, the data were so right-skewed that the usual two-sample t-test could not be considered valid.

The following was repeated 10,000 times. The entire list of $(x_i)_{i=1}^{40}$ was sorted into random order, i.e. a uniformly distributed random permutation $\sigma$ of $\{1,\ldots,40\}$ was chosen, yielding the list $(x_{\sigma(i)})_{i=1}^{40}.$ Then $$ \operatorname{mean}(x_{\sigma(i)})_{i=21}^{40} - \operatorname{mean}(x_{\sigma(i)})_{i=1}^{20} $$ was found. For only $2\%$ of permutations $\sigma$ was the difference in means at least $9.8$ (the difference mentioned above). Thus one can reject the no-difference hypothesis if one is willing to tolerate probability $0.02$ of a false positive.

An obvious reason why one might naively think no deterministic method would work is that computing the difference all $40! \approx 8.16\times 10^{47}$ permutations takes far too long. But that does not prove you can't do something clever with a list of numbers of length only $40$ that could yield an exact result quickly.

Can it be proved that no efficient exact method exists?

2more comments