Axiomas de Blum

En la teoría de la complejidad computacional, los axiomas de Blum o los axiomas de complejidad de Blum son axiomas que especifican las 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 son válidos para cualquier medida de complejidad que satisfaga estos axiomas. Las medidas más conocidas que satisfacen estos axiomas son las del tiempo (es decir, el tiempo de ejecución) y el espacio (es decir, el uso de la memoria).

Definiciones

Una medida de complejidad de Blum es un par con una numeración de Gödel 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 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) requeridos para el cálculo codificado por i .${\displaystyle \Phi }$
• ${\displaystyle (\varphi ,\varphi )}$no es una medida de complejidad, ya que falla el segundo axioma.

Clases de complejidad

Para una complejidad de función computable total, las clases 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 en conjuntos, se pueden considerar como una clase de conjuntos de complejidad.${\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 .