Complexity-Restricted Advice Functions

Johannes Köbler and Thomas Thierauf

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
  1. SPARSE(NP),
  2. NP with a restricted access to an NP oracle, and
  3. 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.