Аксиомы Блюма - Blum axioms

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

Важно отметить, что Теорема Блюма об ускорении и Теорема о разрыве справедливы для любой меры сложности, удовлетворяющей этим аксиомам. Наиболее известные меры, удовлетворяющие этим аксиомам, - это время (то есть время выполнения) и пространство (то есть использование памяти).

Определения

А Мера сложности Блюма пара ${\displaystyle (\varphi ,\Phi )}$ с ${\displaystyle \varphi }$ а Гёделевская нумерация из частичные вычислимые функции ${\displaystyle \mathbf {P} ^{(1)}}$ и вычислимая функция

${\displaystyle \Phi :\mathbb {N} \to \mathbf {P} ^{(1)}}$

который удовлетворяет следующему Аксиомы Блюма. Мы пишем ${\displaystyle \varphi _{i}}$ для я-го частичная вычислимая функция под гёделевской нумерацией ${\displaystyle \varphi }$, и ${\displaystyle \Phi _{i}}$ для частично вычислимой функции ${\displaystyle \Phi (i)}$.

• то домены из ${\displaystyle \varphi _{i}}$ и ${\displaystyle \Phi _{i}}$ идентичны.
• набор ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$ является рекурсивный.

Примеры

• ${\displaystyle (\varphi ,\Phi )}$ является мерой сложности, если ${\displaystyle \Phi }$ время или память (или некоторая подходящая комбинация), необходимые для вычисления, закодированного я.
• ${\displaystyle (\varphi ,\varphi )}$ является нет мера сложности, так как она не соответствует второй аксиоме.

Классы сложности

Для полная вычислимая функция ${\displaystyle f}$ классы сложности вычислимых функций можно определить как

${\displaystyle C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}}$

${\displaystyle C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}}$

${\displaystyle C(f)}$ - множество всех вычислимых функций со сложностью меньше, чем ${\displaystyle f}$. ${\displaystyle C^{0}(f)}$ это набор всех булевозначные функции со сложностью менее ${\displaystyle f}$. Если рассматривать эти функции как индикаторные функции на съемках, ${\displaystyle C^{0}(f)}$ можно рассматривать как сложный класс множеств.

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

1. Блюм, Мануэль (1967). "Машинно-независимая теория сложности рекурсивных функций" (PDF). Журнал ACM. 14 (2): 322–336. Дои:10.1145/321386.321395.