College Publications logo   College Publications title  
View Basket
Homepage Contact page
   
 
AiML
Academia Brasileira de Filosofia
Algorithmics
Cadernos de Lógica e Computação
Cadernos de Lógica e Filosofia
Cahiers de Logique et d'Epistemologie
Communication, Mind and Language
Computing
Cuadernos de lógica, Epistemología y Lenguaje
DEON
Dialogues
Economics
Encyclopaedia of Logic
Filosofia
Handbooks
Historia Logicae
IfColog series in Computational Logic
IfColog Lecture series
IfColog Proceedings
Journals
Journal of Applied Logics - IfCoLoG Journal of Logics and their Applications
About
Editorial Board
Scope of the Journal
Submissions
Forthcoming papers
Law
Logic and Semiotics
Logic PhDs
Logic, Methodology and Philosophy of Science
The Logica Yearbook
Neural Computing and Artificial Intelligence
Philosophy
Research
The SILFS series
Studies in Logic
Studies in Talmudic Logic
Systems
Texts in Logic and Reasoning
Texts in Mathematics
Tributes
Other
Digital Downloads
Information for authors
About us
Search for Books
 



Forthcoming papers


Back

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm

Vanessa Kosoy and Alexander Appel

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.






© 2005–2020 College Publications / VFH webmaster