  We introduce a new concept of approximation applicable to decision problems
and functions, inspired by Bayesian probability. From the perspective of a
Bayesian reasoner with limited computational resources, the answer to a problem
that cannot be solved exactly is uncertain and therefore should be described by
a random variable. It thus should make sense to talk about the expected value
of this random variable, an idea we formalize in the language of average-case
complexity theory by introducing the concept of "optimal polynomial-time
estimators." We prove some existence theorems and completeness results, and
show that optimal polynomial-time estimators exhibit many parallels with
"classical" probability theory.
