Teorema do intervalo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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

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.[2] 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.[3]

Teorema do intervalo[editar | editar código-fonte]

A forma geral do teorema é a seguinte.

Suponha que é uma medida de complexidade abstrata (Blum). Para qualquer função computável total g para o qual para todo , existe uma função computável total t de tal forma que em relação a , as classes de complexidade com funções limitantes e 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 tal que para todo , existe um limite de tempo tal que .

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Fortnow, Lance; Homer, Steve (June 2003). A Short History of Computational Complexity (PDF). Bulletin of the European Association for Theoretical Computer Science. pp. 95–133  Verifique data em: |date= (ajuda)
  2. Boris Trakhtenbrot (1964). Turing computations with logarithmic delay. Algebra and Logic (em Russian). pp. 33–48 
  3. Allan Borodin (1972). Computational complexity and the existence of complexity gaps. Journal of the ACM. pp. 158–174. doi:10.1145/321679.321691