Johannes Köbler and Thomas Thierauf
Abstract:
We consider uniform subclasses of the nonuniform complexity classes
defined by Karp and Lipton via the notion of advice functions. These
subclasses are obtained by restricting the complexity of computing
correct advice. We also investigate the effect of allowing advice
functions of limited complexity to depend on the input rather than on
the input's length. Among other results, using the notions described
above, we give new characterizations of
- SPARSE(NP),
- NP with a restricted access to an NP oracle, and
- the odd levels of the Boolean hierarchy.
As a consequence, we show that every set that is nondeterministically
truth-table reducible to SAT in the sense of Rich is already
deterministically truth-table reducible to SAT. Furthermore, it turns
out that the NP reduction classes of bounded versions of this
reducibility coincide with the odd levels of the Boolean hierarchy.