A characterization of time complexity by simple loop programs

摘要

There is general agreement that computations which are exponentially difficult in time are practically intractable. Thus, even the class L in the hierarchy of Meyer and Ritchie is still inclusive in the sense of practical computability. In this paper, we introduce the notion of simple loop programs, by which we characterize the class L which coincides with the class of Kalmar's elementary functions. We also characterize two hierarchies B0⊆B1⊆B2⋯ and Eξp0⊆Eξp1⊆Eξp2⊆⋯ syntactically. Bk and Eξpk are the classes of languages which can be recognized in O(nκ) times and gκ(p(n)) time, respectively, where g0(n) = n, gκ+1(n) = 2gκ(n), p is a polynomial of n, and n is the length of input. Thus, Uk=0∞Bk=Eξp0 is the class of languages which can be recognized in polynomial time and Uk=0∞Eξpk is the class of elementary problems (i.e., L is in Uk=0∞Eξpk if and only if the characteristic function of L is in L2).