PP-Lowness and a Simple Definition of AWPP |
| |
Authors: | Fenner |
| |
Affiliation: | (1) Computer Science and Engineering Department, University of South Carolina, Columbia, SC 29208, USA fenner@cse.sc.edu, US |
| |
Abstract: | Abstract. We show that the counting classes AWPP and APP FFKL], L] are more robust than previously thought. Our results identify a sufficient 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. We extend a result of K?bler et
al. by proving that all sparse co-C
=
P languages are in APP, and are thus PP-low. Our results also imply that AWPP ⊂eq APP, and thus APP contains many other established subclasses of PP-low, thereby reducing several different lowness results to membership in APP. We also show that AWPP and APP are Σ
0
2
-definable classes. Some of our results are reminiscent of amplifying certainty in probabilistic computation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|