ON SPARSE HARD SETS FOR COUNTING CLASSES

In this paper, we study one-word-decreasing self-reducible sets which are introduced by Lozano and Toran (1991). These are the usual self-re ducible sets with the peculiarity that the self-reducibility machine m akes at most one query and this is lexicographically smaller than the input. We show first that for all counting classes defined by a predic ate on the number of accepting paths there exist complete sets which a re one-word-decreasing self-reducible. Using this fact, we can prove t hat for any class K chosen from {PP, NP, C = P, MOD2 P, MOD3 P,...} it holds that (1) if there is a sparse less-than-or-equal-to(btt)P-hard set for K then K subset-or-equal-to P, and (2) if there is a sparse le ss-than-or-equal-to(btt)SN-hard set for K then K subset-or-equal-to NP and co-NP. This generalizes the result of Ogiwara and Watanabe (1991) to the mentioned complexity classes.