Efficiently approximable real-valued functions

Valentine Kabanets, Charles Rackoff, and Steven A. Cook

Abstract

We define a class, denoted APP, of real-valued functions f:{0,1}n → [0,1] such that f can be approximated, to within any ε > 0, by a probabilistic Turing machine running in time poly(n,1/ε). The class APP can be viewed as a generalization of BPP. We argue that APP is more natural and important than BPP, and that most results about BPP are better stated as results about APP. We show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit. In contrast, no complete problem is known for BPP. We observe that all known complexity-theoretic assumptions under which BPP can be derandomized also allow APP to be derandomized. On the other hand, we construct an oracle under which BPP=P but APP does not collapse to the corresponding deterministic class AP. (However, any oracle collapsing APP to AP also collapses BPP to P.)

Versions