Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-034 | 5th June 2000 00:00

Efficiently Approximable Real-Valued Functions

RSS-Feed




TR00-034
Authors: Valentine Kabanets, Charles Rackoff, Stephen Cook
Publication: 6th June 2000 18:20
Downloads: 1290
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint