Complexity classes with advice
Johannes Köbler, Thomas Thierauf · 2002
A novel concept of nonuniform complexity classes is presented, from which a uniform way of describing known complexity classes is obtained. The usual nonuniform complexity classes introduced by R.M. Karp and R.J. Lipton are modified in two ways: first, not only classes of advice functions defined by pure length bounds are considered, but also limiting the complexity of these functions. In a second step, the advice functions are extended to be functions of the input and not only of the length of the input. With this concept, the certain known language classes are characterized in terms of NP with the advice of certain optimization functions in OptP or of the n-ary characteristic function of SAT.>