Математическая логика и теория алгоритмов

будем считать неопределенным. Функцию S/x) назовем ленточно сложностью. Отметим, что в настоящее время уделяется существенно больше внимания временным характеристикам и значительно меньше емкост­ ным, хотя эта характеристика тоже существенна при использовании ЭВМ с ограниченной памятью. Для задач вводятся понятия задач с полиномиальной потребной памятью, с iVP-потребной памятью и т.д. Имеет место следующая теорема: Теорема 7.2. Для ленточной (емкостной) характеристики сложности вычисления функции/имеет место оценка Sf{x) < x+l+ tf{x), где tf{x) - временная сломсность вычисленияДх). Доказательство, В начальный момент на ленте машины Тьюринга записано число х (в унарной системе), следовательно, занято x+l клеток ленты. На каждом такте (шаге) активной становится не более одной новой клетки, поэтому получим указанную оценку для Sf{x). Эта теорема показывает, что если известна временная слож­ ность, то можно оценить сверху ленточную сложность. Интересно, что нет пределов сложности вычислений. Можно доказать, что какую бы сложную задачу не взять, то существует еще более сложная задача. § 8. Вопросы и темы для самопроверки 1. Понятие о сложности вычислений. 2. Размер исходных данных задачи для случаев, когда входом является число, матрица, граф. 3. Временная сложность алгоритма. Временная сложность задачи. 293