TR00-034 Authors: Valentine Kabanets, Charles Rackoff, Stephen Cook

Publication: 6th June 2000 18:20

Downloads: 2221

Keywords:

We consider a class, denoted APP, of real-valued functions

f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to

within any epsilon>0, by a probabilistic Turing machine running in

time poly(n,1/epsilon). We argue that APP can be viewed as a

generalization of BPP, and show that APP contains a natural

complete problem: computing the acceptance probability of a given

Boolean circuit; in contrast, no complete problems are known for

BPP. We observe that all known complexity-theoretic assumptions

under which BPP is easy (i.e., can be efficiently derandomized)

imply that APP is easy; on the other hand, we show that BPP may

be easy while APP is not, by constructing an appropriate oracle.