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
que satisface los siguientes axiomas de Blum . Nosotros escribimospara la i -ésima función computable parcial bajo la numeración de Gödel, y para la función computable parcial .
Ejemplos de
- 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 .
- no es una medida de complejidad, ya que falla el segundo axioma.
Clases de complejidad
Para una función computable total Las clases de complejidad de funciones computables se pueden definir como
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 puede considerar como una clase de conjuntos de complejidad.
Referencias
- ^ 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 .