Bloom axiómái

A számítási komplexitáselméletben a Bloom -féle axiómák olyan axiómák , amelyek kiszámítható függvények halmazán határozzák meg a bonyolultsági mértékek tulajdonságait . Ezeket az axiómákat először Manuel Blum fogalmazta meg 1967-ben.

Fontos, hogy mind a Blum-féle gyorsulástétel, mind a réstétel igaz legyen minden olyan komplexitásmértékre, amely kielégíti ezeket az axiómákat. Az ilyen intézkedések legismertebb példái a végrehajtási idő (TIME) és a felhasznált memória mennyisége (SPACE).

Definíciók

A Bloom komplexitás mértéke a kiszámítható függvények Gödel-féle felsorolásából és a kiszámítható függvényből álló pár . $(\varphi ,\Phi )$ $\varphi$ ${\displaystyle \mathbf {P} ^{(1)))$

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

kielégítve a következő Bloom-axiómákat . Jelöljük a Gödel-számozás szerinti i - edik kiszámítható függvénnyel , és — a kiszámítható függvénnyel . $\varphi _{i}$ $\varphi$ $\Phi _{i}$ $\Phi (i)$

és tartományai egybeesnek. $\varphi _{i}$ $\Phi _{i}$
a készlet megoldható . ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\))$