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

В теории сложности вычислений теорема Блюма об ускорении , впервые сформулированная Мануэлем Блюмом в 1967 году, является фундаментальной теоремой о сложности вычислимых функций .

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

Если задана мера сложности Блюма и общая вычислимая функция с двумя параметрами, то существует общий вычислимый предикат ( вычислимая функция с булевым значением ), такой что для каждой программы для существует программа для , такая что для почти всех${\displaystyle (\varphi,\Phi)}$${\displaystyle f}$ ${\displaystyle г}$${\displaystyle я}$${\displaystyle г}$${\displaystyle j}$${\displaystyle г}$ ${\displaystyle x}$

${\displaystyle f(x,\Phi _{j}(x))\leq \Phi _{i}(x)}$

${\displaystyle f}$называется функцией ускорения . Тот факт, что она может расти сколь угодно быстро (при условии, что она вычислима), означает, что феномен постоянного наличия программы меньшей сложности сохраняется, даже если под «меньшей» мы подразумеваем «значительно меньшую» (например, квадратично меньшую, экспоненциально меньшую).

• Теорема Гёделя об ускорении

• Блюм, Мануэль (1967). «Машинно-независимая теория сложности рекурсивных функций» (PDF) . Журнал ACM . 14 (2): 322– 336. doi :10.1145/321386.321395. S2CID  15710280.
• Ван Эмде Боас, Питер (1975). «Десять лет ускорения». В Бечварже, Иржи (ред.). Математические основы информатики, 1975 г., 4-й симпозиум, Марианские Лазни, 1–5 сентября 1975 г. Конспекты лекций по информатике. Том. 32. Шпрингер-Верлаг. стр.  13–29 . doi : 10.1007/3-540-07389-2_179. ISBN 978-3-540-07389-5..

• Вайсштейн, Эрик В. «Теорема Блюма об ускорении». MathWorld .