| Abstract: | The article is the text of a survey report on methods of obtaining lower bounds on the computational complexity for abstract computers. Besides the methods for obtaining the lower bounds, related methods for the simulation of some machines by others, with the preservation of some complexity measures at the expense of increase in others (trade-off results), are presented. Methods of crossing sequences, tails, overlaps, and related methods are examined. A new proof of an old result is sometimes given to illustrate the working of a method, or a new result is proved.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 4–24, 1982. |
