Axiomas de Blum - Blum axioms

Na teoria da complexidade computacional, os axiomas de Blum ou axiomas de complexidade de Blum são axiomas que especificam propriedades desejáveis ​​de medidas de complexidade no conjunto de funções computáveis . Os axiomas foram definidos pela primeira vez por Manuel Blum em 1967.

É importante ressaltar que o teorema de aceleração de Blum e o teorema de Gap valem para qualquer medida de complexidade que satisfaça esses axiomas. As medidas mais conhecidas que satisfazem esses axiomas são as de tempo (ou seja, tempo de execução) e espaço (ou seja, uso de memória).

Definições

Uma medida de complexidade Blum é um par com uma numeração das funções computáveis ​​parciais e uma função computável ${\ displaystyle (\ varphi, \ Phi)}$${\ displaystyle \ varphi}$ ${\ displaystyle \ mathbf {P} ^ {(1)}}$

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

que satisfaz os seguintes axiomas de Blum . Escrevemos para a i -ésima função computável parcial sob a numeração de Gödel e para a função computável parcial . ${\ displaystyle \ varphi _ {i}}$${\ displaystyle \ varphi}$${\ displaystyle \ Phi _ {i}}$${\ displaystyle \ Phi (i)}$

• os domínios de e são idênticos.${\ displaystyle \ varphi _ {i}}$${\ displaystyle \ Phi _ {i}}$
• o conjunto é recursivo .${\ displaystyle \ {(i, x, t) \ in \ mathbb {N} ^ {3} | \ Phi _ {i} (x) = t \}}$

Exemplos

• ${\ displaystyle (\ varphi, \ Phi)}$é uma medida de complexidade, se é o tempo ou a memória (ou alguma combinação adequada dos mesmos) necessária para o cálculo codificado por i .${\ displaystyle \ Phi}$
• ${\ displaystyle (\ varphi, \ varphi)}$não é uma medida de complexidade, uma vez que falha no segundo axioma.

Classes de complexidade

Para uma complexidade total de funções computáveis, as classes de funções computáveis ​​podem ser definidas 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)}$é o conjunto de todas as funções computáveis ​​com complexidade menor que . é o conjunto de todas as funções com valor booleano com uma complexidade menor que . Se considerarmos essas funções como funções indicadoras em conjuntos, pode-se pensar em uma classe de complexidade de conjuntos. ${\ displaystyle f}$${\ displaystyle C ^ {0} (f)}$${\ displaystyle f}$${\ displaystyle C ^ {0} (f)}$

Referências