Consider a weather forecaster predicting a probability of rain for
the next day. We consider tests that given a finite sequence of
forecast predictions and outcomes will either pass or fail the
forecaster. Sandroni (2003) shows that any test which passes a
forecaster who knows the distribution of nature, can be
probabilistically passed by a forecaster with no knowledge of
future events.

We look at the computational complexity of such forecasters and
exhibit a linear-time test and a distribution of nature such that
any forecaster without knowledge of the future that can fool the
test must be able to solve PSPACE-hard problems by requiring the
forecaster to simulate a prover in an arbitrary interactive proof
system.