Machine models and linear time complexity

The first of several reasons Linear Time has received relatively little theoretical attention is that no one has given a robust notion of what “Linear Time ” is. Whereas Polynomial Time is the same for just about every sequential model M that has been proposed, almost every two of these models seem to give different definitions of linear time. Two other reasons are that Linear Time seems not to have as many pleasant closure properties as Polynomial Time, and often depends on fussy details of how information is represented. (For instance: Given n integers in the range 1... n 2, should the length of the input be n or ≈ n log n? In linear time, a TM can add integers in standard binary notation but multiplication is considered unlikely; in prime-factor notation, a TM can multiply but likely not add.) However, one of several reasons for the importance of Linear Time is that the frontier of proving lower bounds for natural problems on reasonable models of general-purpose computation has only barely been pushed west of the O(n) Meridian. This survey aims first to put the model-dependence issue into greater focus, and then to provide a new angle for work on lower bounds. Machine models. Suppose that for every machine M1 in model M1 running in time t = t(n) there is a machine M2 in M2 which computes the same partial function in time g = g(t, n). I