DocumentCode :
2722518
Title :
Complexity classes with advice
Author :
Köbler, Johannes ; Thierauf, Thomas
Author_Institution :
Ulm Univ., West Germany
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
305
Lastpage :
315
Abstract :
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
Keywords :
computational complexity; NP; SAT; advice functions; language classes; n-ary characteristic function; nonuniform complexity classes; optimization functions; pure length bounds; Books; Circuits; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113979
Filename :
113979
Link To Document :
بازگشت