Axiomas de Blum

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 inicialmente definidos por Manuel Blum em 1967.

É importante ressaltar que os teoremas da aceleração e do intervalo se mantêm para qualquer medida de complexidade que satisfaz estes axiomas. As medidas mais conhecidas que satisfazem estes axiomas são as medidas de tempo (ou seja, tempo de execução) e espaço (ou seja, uso de memória).

Definições

Uma medida de complexidade de Blum é uma tupla $(\varphi ,\Phi )$ com $\varphi$ um número de Gödel das funções computáveis parciais $\mathbf {P} ^{(1)}$ e uma função computável

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

que satisfaz os seguintes axiomas de Blum. Nós escrevemos $\varphi _{i}$ para a i-ésima função computável parcial sob o número de Gödel $\varphi$, e $\Phi _{i}$ para a função computável parcial $\Phi (i)$.

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

Exemplos

• $(\varphi ,\Phi )$ é uma medida de complexidade, se $\Phi$ é ou o tempo ou a memória (ou ainda, alguma combinação aceitável dos mesmos) necessária para a computação codificada por i.
• $(\varphi ,\varphi )$ não é uma medida de complexidade, uma vez que não satisfaz o segundo axioma.

Notas

Uma medida de complexidade de Blum é definida usando funções computáveis sem nenhuma referência a um modelo de computação específico. A fim de tornar a definição mas acessível, reformulamos os axiomas de blum em termos de máquinas de Turing:

Uma medida de complexidade de Blum é uma função $\Phi$ a partir dos pares (máquina de Turing $M$, entrada $x$ para $M$) para os números naturais em união com infinito. Além disso, $\Phi$ deve satisfazer os seguintes axiomas:

• $\Phi (M,x)$ é finito se e somente se $M(x)$ pára
• Existe um algoritmo que, sobre a entrada $(M,x,n)$, decide se $\Phi (M,x)=n$

Por exemplo, suponha que $\Phi (M,x)$ dê o número de passos de tempo que a máquina M executa sobre a entrada x antes de parar. O primeiro axioma está claro; o segundo segue porque uma máquina de Turing universal pode simular M sobre x enquanto conta os seus passos. Se M excede os n passos, ela pode parar e rejeitar, então não há necessidade de determinar se M pára sobre x.

Classes de complexidade

Para uma função computável total $f$, as classes de complexidade das funções computáveis podem ser definidas como

$C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x\Phi _{i}(x)\leq f(x)\}$

$C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}$

$C(f)$ é o conjunto de todas as funções computáveis com uma complexidade menor do que $f$. $C^{0}(f)$ é o conjunto de todas as funções booleanas com uma complexidade menor do que $f$. Se nós considerarmos essas funções como funções indicadoras sobre conjuntos, $C^{0}(f)$ pode ser pensada como uma classe de complexidade de conjuntos.