Funciones no construibles y resultados anómalos.

En el libro de Arora-Barak, en la definición de funciones construibles en el tiempo, se dice que el uso de funciones que no son construibles en el tiempo puede conducir a "resultados anómalos". ¿Alguien tiene un ejemplo de tal "resultado anómalo"? He escuchado en particular que pueden existir funciones tales que el teorema de la jerarquía del tiempo no se cumple, ¿alguien tiene un ejemplo de tales funciones? ¿Hay algo sobre esto en algún lugar de la literatura?

Teorema de brecha de Borodin : Para cada función computable total , hay una función computable total t tal que D T I M E [ g ( t ( n ) ) ] = D T I M E [ t ( n ) ] .$g(n) \geq n$$t$$DTIME[g(t(n))] = DTIME[t(n)]$

De hecho, esto es válido para cualquier medida de complejidad Blum en lugar de .$DTIME$

Vea también la página de wikipedia y las referencias allí.

Como el artículo de Wikipedia no proporciona la prueba y el documento está en ACM DL, pensé que podría ser útil publicar la prueba aquí:

TEOREMA 3.7. (Teorema de brecha).

Sea una medida de complejidad, g una función recursiva no decreciente tal que ∀ x , g ( x ) ≥ x . Entonces existe una función recursiva creciente t tal que las funciones computables de medida de complejidad t son las mismas que las funciones computables de medida de complejidad g ∘ t .$\Phi$$g$$\forall x, g(x) \geq x$$t$$t$$g\circ t$

PRUEBA.

Defina siguiente manera:$t$

t ( n ) : = μ k > t ( n - 1 ) : ∀ i ≤ n , ( Φ i ( n ) < k ∨ Φ i ( n ) > g ( k )

$$t(0) := 1$$ $$t(n) := \mu{ k > t(n-1)}: \forall i \leq n, (\Phi_i(n)<k \lor \Phi_i(n)> g(k) )$$

1. para todo , hay una k , ya que para todo i ≤ n :$n$$k$$i \leq n$

   $\Phi_i(n)$$\forall k, \Phi_i(n)>g(k)$

   $\Phi_i(n)$$\exists k, \Phi_i(n) < k$

2. $k$$\Phi$$\Phi_i(n) <k$$\Phi_i(n) > g(k)$

3. $t$$n \geq i$$\Phi_i(n) < t(n)$$\Phi_i(n) > g \circ t(n)$

QED

$t$$t(n) > r(n)$

$$t(0) := r(0) + 1$$ $$t(n) := \mu{k > max\{t(n-1), r(n)\}}: \ldots$$

(de Allan Borodin, " Complejidad computacional y la existencia de brechas de complejidad ", JACM 1972, con ligeras modificaciones).