Axiomas de Blum

Axiomas en la teoría de la complejidad computacional

En la teoría de la complejidad computacional, los axiomas de Blum o axiomas de complejidad de Blum son axiomas que especifican propiedades deseables de las medidas de complejidad en el conjunto de funciones computables . Los axiomas fueron definidos por primera vez por Manuel Blum en 1967. ^[1]

Es importante destacar que el teorema de aceleración de Blum y el teorema de brecha son válidos para cualquier medida de complejidad que satisfaga estos axiomas. Las medidas más conocidas que satisfacen estos axiomas son las de tiempo (es decir, tiempo de ejecución) y espacio (es decir, uso de memoria).

Definiciones

Una medida de complejidad de Blum es un par con una numeración de funciones computables parciales y una función computable. ${\displaystyle (\varphi ,\Phi )}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbf {P} ^{(1)}}$

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

que satisface los siguientes axiomas de Blum . Escribimos para la i -ésima función computable parcial bajo la numeración de Gödel , y para la función computable parcial . ${\displaystyle \varphi _{i}}$ ${\displaystyle \varphi }$ ${\displaystyle \Phi _{i}}$ ${\displaystyle \Phi (i)}$

• los dominios de y son idénticos. ${\displaystyle \varphi _{i}}$ ${\displaystyle \Phi _{i}}$
• el conjunto es recursivo . ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}}$

Ejemplos

• ${\displaystyle (\varphi ,\Phi )}$es una medida de complejidad, si es el tiempo o la memoria (o alguna combinación adecuada de los mismos) necesarios para el cálculo codificado por i . ${\displaystyle \Phi }$
• ${\displaystyle (\varphi ,\varphi )}$no es una medida de complejidad, ya que no cumple el segundo axioma.

Clases de complejidad

Para una función computable total, las clases de complejidad de funciones computables se pueden definir como ${\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)}$es el conjunto de todas las funciones computables con una complejidad menor que . es el conjunto de todas las funciones con valores booleanos con una complejidad menor que . Si consideramos esas funciones como funciones indicadoras sobre conjuntos, podemos considerarlas como una clase de complejidad de conjuntos. ${\displaystyle f}$ ${\displaystyle C^{0}(f)}$ ${\displaystyle f}$ ${\displaystyle C^{0}(f)}$

Referencias

1. Blum, Manuel (1967). "Una teoría independiente de la máquina sobre la complejidad de las funciones recursivas" (PDF) . Revista de la ACM . 14 (2): 322–336. doi :10.1145/321386.321395. S2CID  15710280.