Teorema do intervalo

Na teoria da complexidade computacional o teorema do intervalo é um importante teorema sobre a complexidade de funções computáveis.

O teorema afirma que, essencialmente, existem grandes intervalos computáveis na hierarquia das classes de complexidade. Para qualquer função computável que represente um aumento em recursos computacionais, pode-se encontrar um limite do recurso tal que o conjunto das funções computáveis dentro do limite do recurso expandido é o mesmo que o conjunto das computáveis dentro do limite original.

O teorema foi inicialmente descoberto e provado por Boris Trakhtenbrot em 1964, que o publicou em russo e como resultado, recebeu pouca atenção na época da Guerra Fria. Oito anos mais tarde, o mesmo teorema foi publicado por Allan Borodin em 1972 em inglês e recebeu grande atenção, e como resultado, foi chamado de teorema do intervalo de Borodin.

Teorema do intervalo

A forma geral do teorema é a seguinte.

Suponha que $\mathrm{\Phi }$ é uma medida de complexidade abstrata (Blum). Para qualquer função computável total g para o qual $g(x)\ge x$ para todo $x$, existe uma função computável total t de tal forma que em relação a $\mathrm{\Phi }$, as classes de complexidade com funções limitantes $t$ e $g\circ t$ são idênticas.

O teorema pode ser provado usando os axiomas de Blum sem qualquer referências a um modelo computacional concreto, então ele se aplica a tempo, espaço ou qualquer outra medida de complexidade razoável.

Para o caso especial da complexidade de tempo, o teorema pode ser estabelecido de forma mais simples como:

para qualquer função computável total $g:\omega \to \omega$ tal que $g(x)\ge x$ para todo $x$, existe um limite de tempo $T(n)$ tal que $DTIME(g(T(n)))=DTIME(T(n))$.

Como o limite T(n) pode ser bastante grande (e frequentemente será não-construível) o teorema do intervalo não implica nada que seja interessante para classes de complexidade como P ou NP, e não contradiz o teorema de hierarquia de tempo ou o teorema de hierarquia de espaço.

Veja também

• Teorema da aceleração de Blum