Оглавление
Аксиомы Блюма
-
Основы аксиом Блюма
- Аксиомы Блюма определяют желаемые свойства показателей сложности вычислимых функций.
- Сформулированы Мануэлем Блюмом в 1967 году.
-
Теоремы, связанные с аксиомами Блюма
- Теорема Блюма об ускорении и теорема о разрыве применимы к любой мере сложности, удовлетворяющей аксиомам.
-
Примеры показателей сложности
- Время выполнения и использование памяти являются известными показателями, удовлетворяющими аксиомам Блюма.
-
Определение меры сложности Блюма
- Мера сложности Блюма состоит из нумерации частично вычислимых функций и вычислимой функции, удовлетворяющей аксиомам Блюма.
-
Примеры и контрпримеры
- (φ, Φ) является мерой сложности, если Φ – время или объем памяти, необходимые для вычисления закодированного i.
- (φ, φ) не является мерой сложности, так как не соответствует второй аксиоме.
-
Классы сложности
- Для полной функции f классы сложности C(f) и C0(f) определяют множество вычислимых функций с меньшей сложностью, чем f.
- C0(f) можно рассматривать как класс множеств повышенной сложности, если рассматривать их как индикаторные функции.
Полный текст статьи: