DocumentCode
3465896
Title
Logspace self-reducibility
Author
Balcazar, J.L.
Author_Institution
Fac. of Inf., Barcelona Univ. Politecnico de Cataluna
fYear
1988
fDate
14-17 Jun 1988
Firstpage
40
Lastpage
46
Abstract
A definition of self-reducibility is proposed to deal with logarithmic space complexity classes. A general property derived from the definition is used to prove known results comparing uniform and nonuniform complexity classes below polynomial time, and to obtain novel ones regarding nondeterministic nonuniform classes and reducibility to context-free languages
Keywords
context-free languages; context-free languages; logarithmic space complexity classes; logspace self reducibility; nonuniform complexity classes; uniform complexity classes; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location
Washington, DC
Print_ISBN
0-8186-0866-8
Type
conf
DOI
10.1109/SCT.1988.5261
Filename
5261
Link To Document