期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
