Machine models and linear time complexity
Kenneth W. Regan · ACM SIGACT News · 1993
Introduction to Complexity Theory Column 2Every time I see my wife after a while apart--and as until recently we lived on differen t continents, this was not that rare an event-I ' m startled anew by many wonderful facets t o which familiarity will blind me soon thereafter .P and NP are like this too .The friendliness of P and NP became particularly clear to me after I spent some time looking at the (socalled "weak") exponential hierarchy, which is a quite different animal than the polynomial hierarchy.After a while, I realized that the exponential hierarchy ' s behavior (e .g., though P=NP is known to collapse the polynomial hierarchy, E=NE is not known to collapse the exponential hierarchy [Hartmanis, Immerman, and Sewelson, Inf .&Comp., 1985]) was no t strange .The polynomial hierarchy is the fluke (in the example mentioned above, the flukeof-the-day is that the polynomial hierarchy is defined in terms of base and oracle machine s with the same time bounds) .One of polynomial time's nicest features is that most reasonable machine models ca n simulate each other with no more than a (small) polynomial change in run-time .Linear time lacks this feature, and thus the issue of what the right model is becomes central .Below , Ken Regan offers us an insider's guide to linear time, and "nominates . . .leading candidates " for the True Linear Time mantle .