Нижние оценки сложности для машинных моделей вычисления

Статья является текстом обзорного доклада по методам получения нижних оценок вычислительной сложности для абстрактных вычислительных машин. Кроме методов получения нижних оценок излагаются родственные им методы моделирования одних машин другими с сокращением одних мер сложности за счет увеличения других (результаты типа trade-off). Рассматриваются методы следов, хвостов, перекрытий и родственные им методы. В качестве работы метода иногда дается новое доказательство старого результата или доказывается новый результат.