Abstract
In this paper, we study one-word-decreasing self-reducible sets which are introduced by Lozano and Torán (1991). These are the usual self-reducible sets with the peculiarity that the self-reducibility machine makes at most one query and this is lexicographically smaller than the input. We show first that for all counting classes defined by a predicate on the number of accepting paths there exist complete sets which are one-word-decreasing self-reducible. Using this fact, we can prove that for any class
K chosen from {PP, NP, C
= P, MOD
2P, MOD
3 P,…} it holds that (1) if there is a sparse ⩽
P
btt-hard set for
K then
K ⊆ P, and (2) if there is a sparse ⩽
SN
btt-hard set for
K then
K ⊆ NP ⌢ co-NP. This generalizes the result of Ogiwara and Watanabe (1991) to the mentioned complexity classes.
