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

Интересно, что экспоненциальный алгоритм может оказаться при малом размере задачи более быстрым, чем полиномиальный, однако с ростом размера задачи полиномиальный становится более быстрым. Экспоненциальная сложность задачи имеет следующие аспекты: - для отыскания решения требуется экспоненциальное время; - искомое решение может быть настолько велико, что не может быть представлено вырагкением, длина которого была бы ограничена полиномом от длины входа. Вторая ситуация возникает, например, если в задаче коммивоя­ жера требуется найти все маршруты длины, не превосходящей задан­ ной величины L. Может оказаться, что имеется экспоненциальное число маршрутов длины, не превосходящей L. § 7. Ёмкостная (ленточная) сложность алгоритма Емкостная, или ленточная, сложность алгоритма характеризует необходимую для вычисления память для хранения исходных данных, промежуточных результатов и окончательного результата. При при­ менении машины Тьюринга как модели вычислений, емкостная слож­ ность оценивается длиной части ленты, используемой для записи ис­ ходных данных и вычислений. Пусть машина Тьюринга вычисляет значение функции/ Активной зоной ленты (машины Тьюринга) в данный момент времени t называется связанная часть ленты, содержащая обозревае­ мую ячейку и все ячейки, в которых имеются символы из внешнего алфавита машины. Активной зоной при работе машины Тьюринга на числе п называется объединение всех активных зон за время вычисления. Определим S/x) как длину активной зоны при работе машины Т на числе х, если fix) определено. В противном случае значение S/x) 292