Zeitklassen trennen

Ein Student von mir hat kürzlich die folgende Frage gestellt:

Es sei angenommen ,

Dies könnte wahrscheinlich durch die Konstruktion eines h ( n ) als wahr gezeigt werden, $h(n)$wenn $f,g$ sind. Aber im Allgemeinen bin ich der Meinung, dass dies falsch sein sollte, ähnlich wie $DSPACE(o(\log(\log(n)))) = DSPACE(1)$ .

Wenn D T I M E ( f ( n ) ) als die Klasse aller Sprachen definiert ist, die von einer Zwei-Band-Turing-Maschine in O ( f ( n ) ) -Zeit entscheidbar ist , dann vermute ich, dass die Antwort Nein ist. Mit anderen Worten, ich denke, dass es nicht immer eine streng zwischenzeitliche Komplexitätsklasse gibt.$DTIME(f(n))$$O(f(n))$

Hinweis: Diese Antwort ist möglicherweise nicht genau das, wonach Sie suchen, da ich nicht berechenbare Funktionen in Betracht ziehe und nicht jedes Detail des Arguments einbeziehe. Aber ich fand, dass es ein guter Anfang ist. Bitte zögern Sie nicht, Fragen zu stellen. Vielleicht kann ich diese Details irgendwann weiter ausfüllen oder dies führt zu einer besseren Antwort eines interessierten Lesers.

Betrachten Funktionen der Form f : N → N . Wir bezeichnen diese Funktionen als natürliche Zahlenfunktionen.$f : \mathbb{N} \rightarrow \mathbb{N}$

Behauptung 1: Ich behaupte, dass wir eine sehr langsam wachsende nicht abnehmende natürliche Zahlfunktion (nicht berechenbar) ε ( n ) so konstruieren können, dass:$\varepsilon(n)$

(1) $\varepsilon(n)$ is non-decreasing

(2) $\varepsilon(n) = \omega(1)$

(3) Für alle unbegrenzten berechenbaren $f: \mathbb{N} \rightarrow \mathbb{N}$, the set $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ is infinite.

Wir konstruieren ε ( n ) als langsam wachsende, nicht abnehmende Sprungfunktion. Lassen Sie uns alle unbeschränkt berechenbaren Funktionen aufzählen { f i } i ∈ N . Wir wollen ε ( n ) so konstruieren, dass für jedes i und jedes j ≤ $\varepsilon(n)$$\{ f_i \}_{i \in \mathbb{N}}$$\varepsilon(n)$$i$$j \leq i$ , m i n { k|ε ( k ) ≥ i } ≥ m i n { k|f j ( k ) ≥ i } . Mit anderen Worten, wir warten, um ε ( n ) auf i abzubilden,bis die ersten i- Funktionen in der Aufzählungmindestens einmalauf einen Wert größer oder gleich i abgebildet wurden. Dann bildet ε ( n ) weiter auf i ab, bis die ersten i + 1- Funktionen in der Aufzählungmindestens einmalauf einen Wert größer oder gleich i + 1 abgebildet worden sind,und an diesem Punkt beginnt es, auf i + 1 abzubilden$min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$$\varepsilon(n)$$i$$i$$i$$\varepsilon(n)$$i$$i+1$$i+1$$i+1$ . Wenn wir diesen iterativen Prozess zur Konstruktion von $\varepsilon(n)$, then for any given unbounded computable function, although $\varepsilon(n)$ might not always be smaller, it will infinitely often be at least as small.

Note: I just provided some intuition behind claim 1, I did not provide a detailed proof. Please feel free to join in on discussion below.

Because $\varepsilon(n)$ is such a slow growing function, we have the following:

Claim 2: For all computable natural number functions $f(n)$ and $h(n)$, if $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ and $h(n) = O(f(n))$, then $h(n) = \Theta(f(n))$.

For claim 2, if there existed a computable function $h(n)$ between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ such that $h(n) \neq \Theta(f(n))$, then we would be able to compute an unbounded natural number function that grows more slowely than $\varepsilon(n)$ which isn't possible.

Let me explain some relevant details. Suppose for sake of contradiction that such a function $h(n)$ existed. Then, $\lfloor \frac{f(n)}{h(n)} \rfloor$ is unbounded.

Note: The preceding function is computable because $f(n)$ and $h(n)$ are computable.

Since $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$, we have $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$. It follows that there is some constant $\alpha$ such that for all $n$ sufficiently large, $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$. Since this function is unbounded and computable we may apply Claim 1 to get that $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.

Claim 3: For a time constructible function $f(n)$, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$, yet there does not exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$.

In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above). See "The tight deterministic time hierarchy" by Martin Furer.

Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$, we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$, $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$.

If this result is true, it would strengthen the best-known deterministic time hierarchy theorem. [This is more of a comment than an answer, but too long for a comment. It leaves open the direct construction of a counterexample.] Recall that the best Deterministic Time Hierarchy Theorem we currently have is that if $f(n), g(n)$ are time-constructible, and $g(n) \leq o( f(n) / \log f(n) )$, then $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$.

Now suppose your desired result is true, and let $g(n)$ be a time-constructible function that is close to, but still little-oh of, $f(n) / \log(f(n))$, say, $g(n) = f(n) / (\log f(n))^{3/2}$. (This $g$ may not be time-constructible for arbitrary time-constructible $f$, but surely for many time-constructible $f$ this $g$ is also time-constructible.) Now, your desired result produces an $h$ such that $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$. In order to avoid improving the current-best time hierarchy theorem, we would need both $g(n) = o( h(n) / \log(h(n)) )$ and $h(n) = o(f(n) / \log(f(n))$. These two together imply that $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$. Since $h(n) \geq g(n)$, we have $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$, or equivalently $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$. But $g(n) \log(g(n)) = f(n) / (\log(f(n))^{3/2} [\log(f(n)) - (3/2) \log \log(f(n)] \sim f(n) / \sqrt{\log(f(n))}$, which is not $o(f(n) / \log(f(n))$.

I think such a behaviour is true for 1-Tape-DTMs. On the one hand, we have $\mathrm{DTIME}_1(O(n)) = \mathrm{DTIME}_1(o(n \log n))$. Unfortunately, the only reference I know is in German: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8.

On the other hand, it should be possible to separate $\mathrm{DTIME}_1(O(n))$ and $\mathrm{DTIME}_1(O(n \log n))$ by the language $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^* \}$ using a standard crossing sequence argument.