2016/08/14 by Kosoy, Vanessa, Appel, Alexander
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1608.04112
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.