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

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

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

Определения [ править ]

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

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

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

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

Примеры [ править ]

• ${\ 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)}$

Ссылки [ править ]