Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-036 | 30th May 2002 00:00

PP-lowness and a simple definition of AWPP

RSS-Feed




TR02-036
Authors: Stephen A. Fenner
Publication: 19th June 2002 02:10
Downloads: 4738
Keywords: 


Abstract:

We show that the counting classes AWPP and APP [Li 1993] are more robust
than previously thought. Our results identify asufficient condition for
a language to be low for PP, and we show that this condition is at least
as weak as other previously studied criteria. Our results imply that
AWPP is contained in APP, and thus APP contains all other established
subclasses of PP-low. We also show that AWPP and APP are Sigma^0_2
definable classes. Our results are reminiscent of amplifying certainty
in probabilistic computation.



ISSN 1433-8092 | Imprint