Rozdzielanie klas czasowych

Mój student ostatnio zadał następujące pytanie:

D T I M E (f (n)) ⊊ D T I M E (g (n)) .

$DTIME(f(n)) \subsetneq DTIME(g(n)).$

h (n)

$h(n)$

D T I M E (f (n)) ⊊ D T I M E (h (n)) ⊊ D T I M E (g (n)) ?

$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$

Prawdopodobnie można to udowodnić, konstruując jeśli są konstruowalne w czasie. Ale ogólnie uważam, że powinno to być fałszem podobne do . $h(n)$ $f,g$ $DSPACE(o(\log(\log(n)))) = DSPACE(1)$

cc.complexity-theory S. Pek
źródło

Może to zależeć od dokładnego modelu.

Wspomniane tutaj twierdzenie Borodina o luce może być istotne: cstheory.stackexchange.com/questions/8583/…

Michael Wehar

Czy dopuszczasz

f (n), g (n) = O (1)

$f(n),g(n)=O(1)$ ? Ponieważ wtedy musi istnieć jakiś przykład dla niektórych funkcji, które są wszędzie zerowe, z wyjątkiem pierwszego miejsca. W każdym razie, czy to pytanie nie ma sensu, jeśli

f \equiv g

$f\equiv g$ wszędzie oprócz jednego

n

$n$ ?

domotorp

Przykro mi, ale nie do końca podążam za problemem z

f (n), g (n) = O (1)

$f(n),g(n) = O(1)$ jak z definicji

D T I M E (f (n)) = D T I M E (g (n))

$DTIME(f(n))=DTIME(g(n))$ ?

S. Pek

Przepraszam za to, że źle odczytałem pytanie, a mój wcześniejszy komentarz nie miał większego sensu. Usunąłem to. Dziękuję Ci.

Michael Wehar

Odpowiedzi:

Jeśli $DTIME(f(n))$ jest zdefiniowany jako klasa wszystkich języków rozstrzygalnych w czasie $O(f(n))$ przez dwie taśmy Turinga, to podejrzewam, że odpowiedź brzmi „nie”. Innymi słowy, uważam, że nie zawsze istnieje klasa złożoności czasowej ściśle pośredniej.

Uwaga: Ta odpowiedź może nie być dokładnie tym, czego szukasz, ponieważ rozważam funkcje niepoliczalne i nie uwzględniam wszystkich szczegółów argumentu. Ale czułem, że to dobry początek. Zadawaj pytania. Może w którymś momencie mogę uzupełnić te dane, a może doprowadzi to do lepszej odpowiedzi zainteresowanego czytelnika.

Rozważmy funkcje postaci $f : \mathbb{N} \rightarrow \mathbb{N}$ . Te funkcje nazywamy funkcjami liczb naturalnych.

Twierdzenie 1: Twierdzę, że możemy skonstruować bardzo wolno rosnącą, nie malejącą funkcję liczby naturalnej (nieobliczalnej) $\varepsilon(n)$ tak aby:

(1) $\varepsilon(n)$ nie maleje

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

(3) Dla wszystkich nieograniczonych obliczalnych $f: \mathbb{N} \rightarrow \mathbb{N}$ , zbiór $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ jest nieskończone.

Konstruujemy jako wolno rosnącą, nie malejącą funkcję krokową. Pozwól nam wyliczyć wszystkie funkcje obliczalne nieograniczone . Chcemy skonstruować w taki sposób, aby dla każdego i dla każdego , $\varepsilon(n)$ $\{ f_i \}_{i \in \mathbb{N}}$ $\varepsilon(n)$ $i$ $j \leq i$ . Innymi słowy, czekamy na mapowanie na dopóki pierwszefunkcje w wyliczeniu nie zostaną mapowane na wartość większą lub równą przynajmniej raz. Następnie kontynuuje mapowanie do dopóki pierwszefunkcje w wyliczeniu nie zostaną odwzorowane na wartość większą lub równą przynajmniej raz, i w tym momencie zaczyna mapować na $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$ . Jeśli będziemy kontynuować ten iteracyjny proces konstruowania , to dla dowolnej nieograniczonej funkcji obliczeniowej, chociaż nie zawsze może być mniejszy, będzie nieskończenie często co najmniej tak mały. $\varepsilon(n)$ $\varepsilon(n)$

Uwaga: Właśnie przedstawiłem trochę intuicji za twierdzeniem 1, nie przedstawiłem szczegółowego dowodu. Dołącz do dyskusji poniżej.

Ponieważ jest tak wolno rosnącą funkcją, mamy następujące: $\varepsilon(n)$

Twierdzenie 2: Dla wszystkich obliczalnych funkcji liczb naturalnych i , jeśli $f(n)$ $h(n)$ i, a następnie. $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ $h(n) = O(f(n))$ $h(n) = \Theta(f(n))$

2, jeśli istniała obliczalna funkcja między $h(n)$ i, tak że, wówczas będzie mógł obliczyć nieograniczony naturalną funkcję numeryczny, który staje się coraz bardziej powoli a nieco nie jest możliwe . $\frac{f(n)}{\varepsilon(n)}$ $f(n)$ $h(n) \neq \Theta(f(n))$ $\varepsilon(n)$

Pozwól mi wyjaśnić kilka istotnych szczegółów. Załóżmy ze względu na sprzeczność, że taka funkcja istniała. Następnie $h(n)$ jest nieograniczone. $\lfloor \frac{f(n)}{h(n)} \rfloor$

Uwaga: Funkcja poprzedzający obliczeniowy ponieważ i to obliczeniowy. $f(n)$ $h(n)$

Ponieważ , mamy $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ . Wynika z tego, że istnieje pewna stałataka, że dla wszystkichwystarczająco dużych, $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$ $\alpha$ $n$ . Ponieważ ta funkcja jest nieograniczona i obliczalna, możemy zastosować Zastrzeżenie 1, aby uzyskać $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$ nieskończenie często, co jest sprzeczne z poprzednim stwierdzeniem. $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$

Twierdzenie 3: Dla funkcji konstruować w czasie mamy $f(n)$ , alenieistniejetak, że $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ $h(n)$ i $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ . $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$

Aby to pokazać, musimy użyć silniejszego twierdzenia o hierarchii czasu i tutaj przyjmujemy założenie, że liczba taśm jest stała (powiedzieliśmy dwie taśmy powyżej). Patrz „Ścisła deterministyczna hierarchia czasu” Martina Furera. $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$

Ponieważ nie ma obliczalnych funkcji liczb naturalnych między $\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))$ .

Michael Wehar
źródło

Yes, this is exactly what I had in mind too, but then got confused somewhere along the way. I just want to note, that

ϵ (n)

$\epsilon(n)$ needn't be small at all; a similar argument shows that the lower function

\frac{f (n)}{ϵ (n)}

$\frac{f(n)}{\epsilon(n)}$ can be replaced with a function that is always either

f (n)

$f(n)$ or

0

$0$ , and the upper function

f (n) ϵ (n)

$f(n)\epsilon(n)$ can be replaced with a function that is always either

f (n)

$f(n)$ or

\infty

$\infty$ .

domotorp

(3) needs to restrict to unbounded functions

f

$\hspace{.04 in}f$ .

@RickyDemer Yes, you are right! Thank you very much for catching that. I edited my answer to add the word unbounded. :)

Michael Wehar

Im not entirely convinced about Claim 1. Consider

f_{i} (n) = 1

$f_i(n) = 1$ if

n \leq i

$n \leq i$ ,

n - i

$n-i$ otherwise. Considering this enumeration, is

ϵ (n) = Θ (1)

$\epsilon(n) = \Theta(1)$ ?

S. Pek

I have two more concerns of this proof: 1) In claim 2 you said that the contradiction arises from the fact that there cannot exist a computable

ϵ (n)

$\epsilon(n)$ as it equals

| h (n) - f (n) |

$|h(n)-f(n)|$ . I believe this to be a typographical error, as it should say there exist a

k^{'}

$k'$ such that

ϵ (n) = | h (n) - k^{'} \cdot f (n) |

$\epsilon(n) = |h(n) - k'\cdot f(n)|$ . But note that

k^{'}

$k'$

\frac{f (n)}{ϵ (n)}

$\frac{f(n)}{\epsilon(n)}$ need not be time-constructable.

S. Pek

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))$ .

Joshua Grochow
źródło

Cool! Also, note that there is a better time hierarchy theorem if the number of tapes is fixed. See "The tight deterministic time hierarchy" by Martin Furer.

Michael Wehar

@MichaelWehar: Thanks for the pointer! Indeed, when one gets so tight as to only require

g (n) = o (f (n))

$g(n) = o(f(n))$ , as Furer shows when the number of tapes is fixed, then my argument goes away. (And for basically the same reason, my argument goes away if this question were about space hierarchy instead of time: for space we have a perfectly tight hierarchy theorem even if # tapes isn't fixed.)

Joshua Grochow

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.

Markus Bläser
źródło