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 \Phi é uma medida de complexidade abstrata (Blum). Para qualquer função computável total g para o qual g(x) \geq x para todo \,x, existe uma função computável total t de tal forma que em relação a \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) \geq 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[editar | editar código-fonte]

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

  1. Fortnow, Lance. (June 2003). "A Short History of Computational Complexity". Bulletin of the European Association for Theoretical Computer Science (80): 95–133.
  2. Boris Trakhtenbrot. (1964). "Turing computations with logarithmic delay" (em Russian). Algebra and Logic 3 (4): 33–48.
  3. Allan Borodin. (January 1972). "Computational complexity and the existence of complexity gaps". Journal of the ACM 19 (1): 158–174. DOI:10.1145/321679.321691.