Complexity-Restricted Advice Functions
Johannes Köbler, Thomas Thierauf · SIAM Journal on Computing · 1994
The authors consider uniform subclasses of the nonuniform complexity classes defined by Karp and Lipton [L’Enseign. Math., 28 (1982)) via the notion of advice functions. These subclasses are obtained by restricting the complexity of computing correct advice. Also, the effect of allowing advice functions of limited complexity to depend on the input rather than on the input’s length is investigated. Among other results, using the notions described above, new characterizations of (a) ${\text{NP}}^{{\text{NP}} \cap {\text{SPARSE}}} $, (b) ${\text{NP}}$ with a restricted access to an ${\text{NP}}$ oracle, and (c) the odd levels of the boolean hierarchy are given. As a consequence, it is shown that every set that is nondeterministically truth-table reducible to SAT in the sense of Rich [J. Comput. System Sci., 38 (1989), pp. 511–523) 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.