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

Аксиомы теории сложности вычислений

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

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

Определения

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

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

которая удовлетворяет следующим аксиомам Блюма . Запишем для i -й частично вычислимой функции по нумерации Гёделя , а для частично вычислимой функции . ${\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 )}$является мерой сложности, если это либо время, либо память (или некоторая подходящая их комбинация), необходимые для вычисления, кодируемого i . ${\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. doi :10.1145/321386.321395. S2CID  15710280.