24. Меры сложности алгоритмов

Каждая машина Тьюринга T_i с номером i вычисляет для каждого числа n0 функцию _iⁿ от n переменных с номером i. Временной сложностью машины T_i называется функция t_iⁿ, равная числу шагов машины T_i, сделанных при вычислении функции _iⁿ (функция t_iⁿ не определена тогда и только тогда, когда функция _iⁿ не определена). Емкостной сложностью машины T_i называется функция s_iⁿ, равная числу ячеек ленты машины T_i посещаемых в процессе вычисления функции _iⁿ (функция s_iⁿ также не определена тогда и только тогда, когда функция _iⁿ не определена).

Семейство функций {t_iⁿ} называется абстрактной мерой сложности семейства функций {_iⁿ}, если выполнены следующие аксиомы Блюма:

1) для каждого номера i функция t_iⁿ не определена тогда и только тогда, когда функция _iⁿ не определена;

2) для каждого номера i график (t_iⁿ) функции t_iⁿ является разрешимым множеством (определение: _iⁿ{(x₁,…,x_n,y)|yt_iⁿ(x₁,…,x_n,y)}).

Заметим, что график (f_iⁿ) (вычислимой) функции f_iⁿ является только перечислимым множеством. Напомним, что множество ANⁿ является перечислимым (разрешимым), если существует алгоритм, который для каждого числового вектора x(x₁,…,x_n) на вопрос "xA?" отвечает положительно, если xA, и не отвечает (отвечает отрицательно), если xA.

Временная и емкостная сложности машин Тьюринга являются абстрактными мерами сложности (удовлетворяют аксиомам Блюма).

Результаты о мерах сложности, которые выводятся из свойств вычислимых функций и аксиом Блюма, называются машинно-независимыми.

Теорема «сжимания» Рабина.

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

1) наличие эффективного списка _iⁿ всех частично рекурсивных n-местных функций;

2) теорема о существовании универсальной функции для _iⁿ;

3) теорема параметризации (или s-m-n-теорема);

4) аксиомы Блюма.

Приведем без доказательства две машинно-независимые теоремыо сложности: теорему сжимания Рабина и теорему ускорения Блюма.

Для любой рекурсивной функции есть бесконечно много машин Тьюринга, ее вычисляющих. Некоторые рекурсивные функции настолько каверзные, что любой вычисляющей их машине требуется очень длительное время.

Теорема 1. Для всякой общерекурсивной функция h(x) существует общерекурсивная функция f(x) со значениями 0,1, которая вычисляется машиной Тьюринга T_i, так, что t_i(x)h(x) для всех xx₀ для некоторого числа x₀.

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

Теорема ускорения Блюма.

Следующая теорема утверждает, что существует функция, которая не обязана иметь самый быстрый индекс.

Теорема 1. Для всякой общерекурсивной функция r(x) существует общерекурсивная функция f(x) со значениями 0,1, которая вычисляется машиной Тьюринга T_i, и для которой найдется машина Тьюринга T_j, вычисляющая тоже функцию f(x), такая, что r(t_j(x))t_i(x) для всех xx₀ для некоторого числа x₀.

Если, например, r(x)2^x, то запись 2^tj(x)t_i(x) означает, что для любой машины, вычисляющей f(x), существует другая машина, вычисляющая f(x), экспоненциально быстрее почти для всех входов.