Nicht konstruierbare Funktionen und anomale Ergebnisse

Im Arora-Barak-Buch wird bei der Definition von zeitkonstruierbaren Funktionen gesagt, dass die Verwendung von Funktionen, die nicht zeitkonstruierbar sind, zu "anomalen Ergebnissen" führen kann. Hat jemand ein Beispiel für ein solches "anomales Ergebnis"? Ich habe insbesondere gehört, dass es Funktionen geben könnte, die so gelten, dass der Zeithierarchiesatz nicht gilt. Hat jemand ein Beispiel für solche Funktionen? Gibt es irgendwo in der Literatur etwas darüber?

Borodins Lückensatz : Für jede insgesamt berechenbare Funktion gibt es eine insgesamt berechenbare Funktion so dass .t 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)]$

Tatsächlich gilt dies für jedes Blum-Komplexitätsmaß anstelle von .$DTIME$

Siehe auch die Wikipedia-Seite und die darin enthaltenen Referenzen.

Da der Wikipedia-Artikel den Beweis nicht liefert und das Papier auf ACM DL ist, dachte ich, dass es nützlich sein könnte, den Beweis hier zu posten:

Satz 3.7. (Lückensatz).

Sei ein Komplexitätsmaß, eine nicht abnehmende rekursive Funktion, so dass . Dann existiert eine zunehmende rekursive Funktion so dass Funktionen, die aus dem Komplexitätsmaß werden können, dieselben sind wie Funktionen, die aus dem Komplexitätsmaß .g ∀ x , g ( x ) ≥ x t t g ∘ $\Phi$$g$$\forall x, g(x) \geq x$$t$$t$$g\circ t$

BEWEIS.

Definieren Sie wie folgt:$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. für alle gibt es ein , da für alle :k i ≤ $n$$k$$i \leq n$

   ein. Wenn undefiniert ist, dann ist und$\Phi_i(n)$$\forall k, \Phi_i(n)>g(k)$

   b. Wenn definiert ist, dann .$\Phi_i(n)$$\exists k, \Phi_i(n) < k$

2. $k$ kann rekursiv gefunden werden, da ein Komplexitätsmaß ist und somit und rekursive Prädikate sind.$\Phi$$\Phi_i(n) <k$$\Phi_i(n) > g(k)$

3. $t$ erfüllt den Satz, da impliziert, dass entweder oder .$n \geq i$$\Phi_i(n) < t(n)$$\Phi_i(n) > g \circ t(n)$

QED.

Wir beobachten, dass ein beliebig großes kann, um Satz 3.7 zu erfüllen. Angenommen, wir wollen und definieren dann$t$$t(n) > r(n)$

t ( n ) : = μ k > m a x { t ( n - 1 ) , r ( n ) } :

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

(von Allan Borodin, " Computerkomplexität und das Vorhandensein von Komplexitätslücken ", JACM 1972, mit geringfügigen Modifikationen.)