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