6.4 Теорема об ускорении

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

Существуют функции, которые можно вычислять ве быстрее и быстрее почти всюду, а именно: пусть М₁ – некоторая МНР, вычисляющая функцию f(n), пусть t₁(n) – время ее работы.

Тогда существует машина М₂, которая также вычисляет функцию f(n), причем для почти всех n время ее работы t₂(n)≤𝜑(t₁(n)), где 𝜑 – произвольная функция ускорения со свойствами

.

^n→∞

Комментарий. Если φ(n)=

100 раз быстрее машины М_1.

Если φ(n)=, то ускорение уже происходит не в разы, а на порядок.

Без доказательства.

Таким образом, нашу функцию f мы можем вычислять все быстрее и быстрее, но при этом исключительное множество( множество чисел, для которых ускорение не происходит) становится все больше.

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