Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1608.04112 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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.