Аксиомы Блюма

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

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

Определения

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

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

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

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

Примеры

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

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

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

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

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

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