TR06-149 Authors: Lance Fortnow, Rakesh Vohra

Publication: 11th December 2006 10:00

Downloads: 2450

Keywords:

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.