2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace

При написании этого раздела использовались материалы курсы лекций [1].

После определения разрешимости хочется иметь меру сложности вычисления. Здесь и дальше мы будем рассматривать только разрешимые задачи и всюду определенные (не зацикливающиеся ни на одном входе) машины Тьюринга. Под временем вычисления будем понимать число шагов машины Тьюринга до получения результата.

Определение 8. Пусть . Машина Тьюринга T имеет временную сложность t(n), если для каждого входного слова длины n T выполняет не больше t(n) шагов до остановки. Также будем обозначать временную сложность машины Тьюринга T, как timeT (n).

Используемой памятью будем считать число ячеек на ленте, использованных для записи, не считая длины входа.

Определение 9. Ленточной сложностью машины Тьюринга называется функция , которая равна мощности просматриваемой активной зоны ленты (исключая мощность входного слова).

Обратите внимание, что пространственная сложность может быть меньше длины входа.

Следующим шагом могло бы стать разумное определение «оптимального» алгоритма для данной алгоритмической задачи.

К сожалению, такой подход оказался бесперспективным, и соответствующий результат (теорема об ускорении), установленный на заре развития теории сложности вычислений М. Блюмом , послужил на самом деле мощным толчком для ее дальнейшего развития. Приведем этот результат (без доказательства).

Теорема 2. Существует разрешимая алгоритмическая задача, для которой выполнено следующее. Для произвольного алгоритма A, решающего эту задачу и имеющего сложность в наихудшем случае timeA(n), найдется другой алгоритм B (для этой же задачи) со сложностью timeB(n), такой, что

выполнено для почти всех n (т.е. для всех n, начиная с некоторого).

Эта теорема показывает, что любой вычислительный процесс машины Тьюринга можно улучшить с некоторого шага на МТ , что в свою очередь с некоторого шага улучшается на МТ и т.д. Тем самым не существует вычисления наилучшего а абсолютном смысле.

Следует сразу отметить, что задача, о которой идет речь в этой теореме, выглядит довольно искусственно, и, по-видимому, ничего подобного не происходит для задач, реально возникающих на практике. Тем не менее, теорема об ускорении не позволяет нам определить общее математическое понятие «оптимального» алгоритма, пригодное для всех задач, поэтому развитие теории эффективных алгоритмов пошло другим путем. Именно, одним из центральных понятий этой теории стало понятие класса сложности.

Так называется совокупность тех алгоритмических задач, для которых существует хотя бы один алгоритм с теми или иными сложностными характеристиками.