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

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

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

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

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

${\ Displaystyle е (х, \ Phi _ {j} (x)) \ leq \ Phi _ {i} (x) \,}$

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

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

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

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

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

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

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