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

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

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

Определения

Блюм мера сложности является пара с в нумерации из частичных вычислимых функций и вычислимой функции ${\ 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 С ^ {0} (е): = \ {ч \ ин С (е) | \ mathrm {codom} (ч) \ substeq \ {0,1 \} \}}$

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

использованная литература