Title :
Recursion theoretic characterizations of complexity theoretic properties
Author :
Bennison, Victor L. ; Soare, Robert I.
fDate :
Oct. 31 1977-Nov. 2 1977
Abstract :
In this paper we exhibit recursion theoretic characterizations for two types of r.e. complexity sequences and use these characterizations to prove interesting facts about the classes of sets (or functions) possessing such complexity sequences.
Keywords :
Computational complexity; Cost function; Mathematics;
Conference_Titel :
Foundations of Computer Science, 1977., 18th Annual Symposium on
Conference_Location :
Providence, RI, USA
DOI :
10.1109/SFCS.1977.26