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 , 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 em 1972 em inglês e recebeu grande atenção, e como resultado, foi chamado de teorema do intervalo de Borodin.