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

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

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

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

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

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

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

См. также

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

Ссылки

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

Внешние ссылки

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