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

Более того, $\mathbf{K}$ ограничено линейной функцией, но ${\mathbf{K}}^{-1}$ не ограничено никакой рекурсивной функцией.
Доказательство.
Используем колмогоровскую меру сложности. Для рекурсивной функции $u:\mathbf{N}\to \mathbf{N},x\in \mathbf{N}$, положим $C_u(x):=min\{k\mid f(k)=x\}$, или $\mathrm{\infty }$, если такое $k$ не существует. Назовем такую функцию $u$ оптимальной, если для любой другой рекурсивной функции $v$ существует такая константа $c_{u,v}$, что $C_u(x)⩽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)=\exp (O(1))C_u(x).$$
классической ситуации (23) может сыграть роль в изучении лимитирующего поведения алгоритмов, полиномиальных по времени, как было предложено в [Fr1] и [Fr2].

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