Constant time factors do matter (extended abstract

The constant speedup theorem, so well known from Tur-ing machine based complexity theory, is shown false for a natural imperative programming language I that ma-nipulates tree-structured data. This relieves a tension between general programming practice, where linear fac-tors are essential, and complexity theory, where linear time changes are traditionally regarded as trivial. Specifically, there is a constant b such that for any a> 0 there is a set X recognizable in time1 a · b · n but not in time a · n. Thus LIN, the collection of all sets recognizable in linear time by deterministic I-programs, contains an infinite hierarchy ordered by constant coef-ficients. Constant hierarchies also exist for larger time bounds T (n), provided they are time-constructable. Second, a problem is exhibited which is complete for the nondeterministic linear time sets NLIN with respect to a natural notion of deterministic linear-time reduction. Third, Kleene’s Second Recursion Theorem in essence shows that for any program p defined with self-reference, there is an equivalent nonreflexive program q. This is proven for an extension I ↑ of I. Further, q can be sim-ulated by an I program at most constantly slower than p. Language I ↑ allows calls to the language’s own inter-pretation function, and even to its running time function (without the usual high costs for nested levels of inter-pretation). The results all hold as well for a stronger language Isu allowing selective updating of tree-structured data. The results are robust in that classes LINsu and NLINsu are identical for Isu, Isu↑, Schönhage’s Storage Modifi-cation Machines, Knuth/Tarjan’s pointer machines, and successor RAMs2 [13,14,11]. 1where n is the size of the input