Теорема Блюмса об ускорении - Blums speedup theorem

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

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

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

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

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

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

Смотрите также

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

Рекомендации

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

внешняя ссылка

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