Title :
Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
Author :
Krause, Matthias ; Meinel, Christoph ; Waack, Stephan
Author_Institution :
Sektion Math., Humboldt Univ., Berlin, East Germany
Abstract :
It is proved that oblivious simultaneously linear access-time and logarithmic space-bounded nondeterministic Turing machines are more powerful than deterministic ones. All the corresponding complexity classes are separated from each other
Keywords :
Turing machines; computational complexity; complexity classes; input oblivious logarithmic space-bounded Turing machines; linear access-time; Binary decision diagrams; Complexity theory; Microwave integrated circuits; Polynomials; Turing machines; Upper bound;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41831
