Separating Nondeterministic Time Complexity Classes
Joel Seiferas, Michael J. Fischer, Albert R. Meyer · Journal of the ACM · 1978
AaSTancr.A recurslve padding technique is used to obtain conditions sufficient for separation of nondetermlmsttc multltape Turlng machine time complexity classes If T2 is a running time and Tl(n + 1) grows more slowly than T~(n), then there is a language which can be accepted nondetermmlstlcally within time bound T~ but which cannot be accepted nondetermlnlStlcally within time bound T1.If even T~(n + f(n)) grows more slowly than Tz(n), where f is the very slowly growing "rounded reverse" of some real-time countable function, then there is such a language over a single-letter alphabet.The strongest known dmgonalization results for both deterministic and nondetermlmstlc time complexity classes are reviewed and orgamzed for comparison with the results of the new padding technique KEY WOADS ^NO PHaASrS: Turlng machine, complexity class, complexity hierarchy, time complexity, nondetermmism, padding, recursmn theorem, dmgonahzatmn, single-letter alphabet CR CAa~ORIES 5 23, 5.25, 5.26, 5 27 This paper represents a portion of the first author's Ph D d~ssertatlon [25] written at M.