Существует такая перестановка $\mathbf{K}: \mathbf{N} \rightarrow \mathbf{N}$, что для любой частично-рекурсивной функции $f: \mathbf{N} \rightarrow \mathbf{N}$ существует константа с со свойством
\[
\mathbf{K} \circ f \circ \mathbf{K}^{-1}(n) \leqslant c n \text { для всех } n \in \mathbf{K}(D(f)) .
\]

Более того, $\mathbf{K}$ ограничено линейной функцией, но $\mathbf{K}^{-1}$ не ограничено никакой рекурсивной функцией.
Доказательство.
Используем колмогоровскую меру сложности. Для рекурсивной функции $u: \mathbf{N} \rightarrow \mathbf{N}, x \in \mathbf{N}$, положим $C_{u}(x):=\min \{k \mid f(k)=x\}$, или $\infty$, если такое $k$ не существует. Назовем такую функцию $u$ оптимальной, если для любой другой рекурсивной функции $v$ существует такая константа $c_{u, v}$, что $C_{u}(x) \leqslant c_{u, v} C_{v}(x)$ для любых $x$. Оптимальные функции действительно существуют (см., например, [Ma1], теорема VI.9.2); в частности, они принимают все положительные целые значения (однако, они, конечно, не являются всюду определенными). Зафиксируем одно такое $u$ и назовем $C_{u}(x)$ (экспоненциальной) сложностью $x$. По определению, $\mathbf{K}=\mathbf{K}_{u}$ переупорядочивает $\mathbf{N}$ в порядке возрастания сложности. Другими словами,
\[
\mathbf{K}(x):=1+\operatorname{card}\left\{y \mid C_{u}(y)<C_{u}(x)\right\} .
\]

Сначала мы покажем, что
\[
\mathbf{K}(x)=\exp (O(1)) C_{u}(x) .
\]
классической ситуации (23) может сыграть роль в изучении лимитирующего поведения алгоритмов, полиномиальных по времени, как было предложено в [Fr1] и [Fr2].

В заключение я хотел бы прокомментировать скрытую роль колмогоровской сложности в реальной жизни классических вычислений. Дело в том, что в некотором смысле (который трудно формализовать) нас интересует только вычисление достаточно хороших функций, так как случайная логическая функция в любом случае будет иметь (супер)экспоненциальную сложность. Хорошая функция, по крайней мере, имеет короткое описание и, поэтому, малую колмогоровскую сложность. Таким образом, имея дело с практическими проблемами, мы в действительности работаем не с малыми числами, графами, схемами, …, а, скорее, с начальным сегментом соответствующего конструктивного мира, переупорядоченного с помощью К. Мы систематически заменяем большой объект его коротким описанием и затем пытаемся преодолеть вычислительные трудности, порожденные этой заменой.