Logarithmic advice classes

Karp and Lipton (1980) introduced the notion of nonuniform complexity classes where a certain amount of additional information, the advice, is given for free. The advice only depends on the length of the input. Karp and Lipton initiated the study of classes with either logarithmic or polynomial advice; however, later Yap (1983), Schöning (1984), Balcázar (1987) and Ko and Schöning (1985) concentrated on the study of classes of the form C /poly, where C is P, NP, or PSPACE, and poly denotes a polynomial-size advice. This paper considers classes of the form C /log. As a main result it is shown that in the context of an NP/log computation, log-bounded advice is equivalent to a sparse oracle in NP. In contrast, it has been shown that a poly-bounded advice to an arbitrary sparse oracle set. Furthermore, a general theorem is presented that generalizes Karp and Lipton's “round-robin tournament” method.

Authors

• JoséL. Balcázar
• Uwe Schöning

Keywords

No keywords are indexed for this paper.