Title :
Translational methods and computational complexity
Author :
Ruby, S.S. ; Fischer, P.C.
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;
Conference_Titel :
Switching Circuit Theory and Logical Design, 1965. SWCT 1965. Sixth Annual Symposium on
Conference_Location :
Ann Arbor, MI, USA
DOI :
10.1109/FOCS.1965.33