DocumentCode :
3263861
Title :
Translational methods and computational complexity
Author :
Ruby, S.S. ; Fischer, P.C.
fYear :
1965
fDate :
6-8 Oct. 1965
Firstpage :
173
Lastpage :
178
Abstract :
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A "translational" method which escapes some of the limitations of earlier approaches leads to a refinement of the established hierarchy. The previous complexity classes are shown to possess certain translational properties. An related hierarchy of complexity classes of monotonic functions is examined
Keywords :
Binary sequences; Computational complexity; Ear; Magnetic heads; RNA; Reactive power; Read only memory; Turing machines; Weight control;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Switching Circuit Theory and Logical Design, 1965. SWCT 1965. Sixth Annual Symposium on
Conference_Location :
Ann Arbor, MI, USA
Type :
conf
DOI :
10.1109/FOCS.1965.33
Filename :
5397247
Link To Document :
بازگشت