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 ${\displaystyle \Phi }$ é uma medida de complexidade abstrata (Blum). Para qualquer função computável total g para o qual ${\displaystyle g(x)\geq x}$ para todo ${\displaystyle \,x}$, existe uma função computável total t de tal forma que em relação a ${\displaystyle \Phi }$, as classes de complexidade com funções limitantes ${\displaystyle t}$ e ${\displaystyle 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 ${\displaystyle g\,:\,\omega \,\to \,\omega }$ tal que ${\displaystyle g(x)\geq x}$ para todo ${\displaystyle \,x}$, existe um limite de tempo ${\displaystyle T(n)}$ tal que ${\displaystyle 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.

Ver também

• Teorema da aceleração de Blum

Referências