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

редактировать

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

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

Содержание

1 Определения
- 1.1 Примеры
2 Классы сложности
3 Ссылки

Определения

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

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

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

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

домены из $φ i {\ displaystyle \ varphi _ {i}}$ $\ varphi _ {i}$ и $Φ i {\ displaystyle \ Phi _ {i}}$ $\ Phi _ { i}$ идентичны.
множество ${(i, x, t) ∈ N 3 | Φ я (Икс) знак равно T} {\ Displaystyle \ {(я, х, т) \ в \ mathbb {N} ^ {3} | \ Phi _ {я} (х) = т \}}$ $\ {(i, x, t) \ in {\ mathbb {N}} ^ {3} | \ Phi _ {i} (x) = t \}$ является рекурсивным.

Примеры

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

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

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

C (f): = {φ i ∈ P (1) | ∀ х. Φ я (Икс) ≤ е (Икс)} {\ Displaystyle C (F): = \ {\ varphi _ {i} \ in \ mathbf {P} ^ {(1)} | \ forall x. \ \ Phi _ {i} (x) \ leq f (x) \}}

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

C 0 (f): = {h ∈ C (f) | кодом (час) ⊆ {0, 1}} {\ displaystyle C ^ {0} (f): = \ {h \ in C (f) | \ mathrm {codom} (h) \ substeq \ {0,1 \ } \}}

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

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

Ссылки