Title :
Logspace self-reducibility
Author_Institution :
Fac. of Inf., Barcelona Univ. Politecnico de Cataluna
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5261
