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 Gap se cumplen para cualquier medida de complejidad que satisfaga estos axiomas. Las medidas más conocidas que satisfacen estos axiomas son las de tiempo (es decir, el tiempo de ejecución) y espacio (es decir, el uso de la memoria).

Definiciones

Una medida de complejidad de Blum es un par con una numeración de las 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 parcial computable bajo la numeración de Gödel , y para la función parcial computable . ${\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 ambos) requerida 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 de valor booleano con una complejidad menor que . Si consideramos esas funciones como funciones indicadoras en conjuntos, se puede pensar en ellas 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 de la complejidad de las funciones recursivas" (PDF) . Revista de la ACM . 14 (2): 322–336. doi :10.1145/321386.321395. S2CID  15710280.