Séparation des classes horaires

Un de mes étudiants a récemment posé la question suivante:

SupposonsDoit-il exister un tel que

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

Cela pourrait probablement être démontré en construisant un $h(n)$ si $f,g$ sont constructibles dans le temps. Mais en général, je pense que cela devrait être faux similaire à $DSPACE(o(\log(\log(n)))) = DSPACE(1)$ .

cc.complexity-theory S. Pek
la source

Cela peut dépendre du modèle précis.

Le théorème de l'écart de Borodine mentionné ici peut être pertinent: cstheory.stackexchange.com/questions/8583/…

Michael Wehar

Autorisez-vous

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

$f(n),g(n)=O(1)$ ? Parce qu'alors, un exemple doit exister pour certaines fonctions qui sont nulles partout, sauf la première place. Quoi qu'il en soit, cette question n'a-t-elle aucun sens si

f \equiv g

$f\equiv g$ partout sauf un

n

$n$ ?

domotorp

Je suis désolé de ne pas suivre tout à fait le problème avec

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

$f(n),g(n) = O(1)$ comme par définition

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

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

S.Pek

Désolé, j'ai mal lu la question et mon commentaire précédent n'avait pas beaucoup de sens. Je l'ai retiré. Je vous remercie.

Michael Wehar

Réponses:

Si est défini comme la classe de toutes les langues décidables en temps par une machine de Turing à deux bandes, alors je soupçonne que la réponse est non. En d'autres termes, je pense qu'il n'existe pas toujours une classe de complexité temporelle strictement intermédiaire. $DTIME(f(n))$ $O(f(n))$

Remarque: Cette réponse n'est peut-être pas exactement ce que vous recherchez, car je considère les fonctions non calculables et je n'inclus pas tous les détails de l'argument. Mais j'ai senti que c'était un bon début. N'hésitez pas à poser des questions. Je pourrais peut-être compléter ces détails à un moment donné ou peut-être que cela mènera à une meilleure réponse d'un lecteur intéressé.

Considérons les fonctions de la forme . Nous appelons ces fonctions des fonctions de nombres naturels. $f : \mathbb{N} \rightarrow \mathbb{N}$

Allégation 1: Je prétends que nous pouvons construire une fonction de nombre naturel non décroissant (non calculable) à croissance très lente telle sorte que: $\varepsilon(n)$

(1) n'est pas décroissant $\varepsilon(n)$

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

(3) Pour tout calculable non borné , l'ensemble est infini. $f: \mathbb{N} \rightarrow \mathbb{N}$ $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$

Nous construisons comme une fonction de pas non décroissante à croissance lente. Énumérons toutes les fonctions calculables illimitées . Nous voulons construire de telle sorte que pour chaque et chaque , . En d'autres termes, nous attendons de mapper à jusqu'à ce que les premières fonctions de l'énumération soient mappées à une valeur supérieure ou égale à au moins une fois. Ensuite, continue de mapper vers $\varepsilon(n)$ $\{ f_i \}_{i \in \mathbb{N}}$ $\varepsilon(n)$ $i$ $j \leq i$ $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$ $\varepsilon(n)$ $i$ $i$ $i$ $\varepsilon(n)$ $i$ jusqu'à ce que les premières fonctions de l'énumération soient mappées à une valeur supérieure ou égale à au moins une fois et à ce stade, elle commence à être mappée à . Si nous continuons ce processus itératif pour construire , alors pour toute fonction calculable non bornée donnée, bien que ne soit pas toujours plus petit, il sera infiniment souvent au moins aussi petit. $i+1$ $i+1$ $i+1$ $\varepsilon(n)$ $\varepsilon(n)$

Remarque: Je viens de fournir une intuition derrière la revendication 1, je n'ai pas fourni de preuve détaillée. N'hésitez pas à vous joindre à la discussion ci-dessous.

Parce que est une fonction à croissance si lente, nous avons ce qui suit: $\varepsilon(n)$

Allégation 2: pour toutes les fonctions de nombres naturels calculables et , si et , puis . $f(n)$ $h(n)$ $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ $h(n) = O(f(n))$ $h(n) = \Theta(f(n))$

Pour la revendication 2, s'il existait une fonction calculable entre et telle que , alors nous pourrions calculer une fonction de nombre naturel illimitée qui croît plus lentement que ce qui n'est pas possible. $h(n)$ $\frac{f(n)}{\varepsilon(n)}$ $f(n)$ $h(n) \neq \Theta(f(n))$ $\varepsilon(n)$

Permettez-moi d'expliquer certains détails pertinents. Supposons par souci de contradiction qu'une telle fonction existe. Ensuite, est illimité. $h(n)$ $\lfloor \frac{f(n)}{h(n)} \rfloor$

Remarque: La fonction précédente est calculable car et sont calculables. $f(n)$ $h(n)$

Puisque , nous avons . Il s'ensuit qu'il existe une constante telle que pour tout suffisamment grand, . Puisque cette fonction est illimitée et calculable, nous pouvons appliquer la revendication 1 pour obtenir ce infiniment souvent, ce qui contredit la déclaration précédente. $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$ $\alpha$ $n$ $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$ $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$

Revendication 3: Pour une durée fonction constructible , nous avons cette , mais il ne pas existe tel que et . $f(n)$ $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ $h(n)$ $\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))$

Afin de montrer simplement que, nous devons utiliser un théorème de hiérarchie temporelle plus fort et c'est là que nous utilisons le hypothèse que le nombre de bandes est fixe (nous avons dit deux bandes ci-dessus). Voir "La stricte hiérarchie déterministe du temps" par Martin Furer. $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$

Puisqu'il n'y a pas de fonctions de nombres naturels calculables entre et autres que celles qui sont , nous avons cela pour chaque fonction tel que et , . $\frac{f(n)}{\varepsilon(n)}$ $f(n)$ $\Theta(f(n))$ $h(n)$ $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ $h(n) \neq \Theta(f(n))$ $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$

Michael Wehar
la source

Oui, c'est exactement ce à quoi je pensais aussi, mais je me suis ensuite confus quelque part en cours de route. Je veux juste noter que n'a pas du tout besoin d'être petit; un argument similaire montre que la fonction inférieure peut être remplacée par une fonction qui est toujours soit ou , et la fonction supérieure peut être remplacé par une fonction qui est toujours soit soit .

ϵ (n)

$\epsilon(n)$

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

$\frac{f(n)}{\epsilon(n)}$

f (n)

$f(n)$

0

$0$

f (n) ϵ (n)

$f(n)\epsilon(n)$

f (n)

$f(n)$

\infty

$\infty$

domotorp

(3) doit se limiter aux fonctions illimitées .

f

$\hspace{.04 in}f$

@RickyDemer Oui, vous avez raison! Merci beaucoup d'avoir compris cela. J'ai modifié ma réponse pour ajouter le mot sans limite. :)

Michael Wehar

Je ne suis pas entièrement convaincu de la revendication 1. Considérons si , sinon. Compte tenu de cette énumération, est ?

f_{i} (n) = 1

$f_i(n) = 1$

n \leq i

$n \leq i$

n - i

$n-i$

ϵ (n) = Θ (1)

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

S.Pek

J'ai deux autres préoccupations concernant cette preuve: 1) Dans la revendication 2, vous avez dit que la contradiction vient du fait qu'il ne peut exister un calculable car il est égal à. Je pense que c'est une erreur typographique, car il faut dire qu'il existe un tel que. Mais notez que n'a pas besoin d'être calculable, donc l'argument n'a pas besoin de tenir. 2) Vous avez utilisé le résultat de Furer dans la revendication 3. Cependant, le résultat n'est valable que pour les fonctions constructibles dans le temps, mais n'a pas besoin d'être constructible dans le temps.

ϵ (n)

$\epsilon(n)$

| h (n) - f (n) |

$|h(n)-f(n)|$

k^{'}

$k'$

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

$\epsilon(n) = |h(n) - k'\cdot f(n)|$

k^{'}

$k'$

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

$\frac{f(n)}{\epsilon(n)}$

S.Pek

Si ce résultat est vrai, il renforcerait le théorème de la hiérarchie temporelle déterministe le plus connu. [C'est plus un commentaire qu'une réponse, mais trop long pour un commentaire. Cela laisse ouverte la construction directe d'un contre-exemple.] Rappelons que le meilleur théorème de la hiérarchie temporelle déterministe que nous avons actuellement est que si sont constructibles dans le temps, et , puis . $f(n), g(n)$ $g(n) \leq o( f(n) / \log f(n) )$ $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$

Supposons maintenant que le résultat souhaité soit vrai, et que soit une fonction constructible dans le temps qui soit proche, mais toujours peu oh, de , disons, . (Ce peut ne pas être constructible dans le temps pour arbitrairement constructible dans le temps , mais sûrement pour de nombreux constructibles dans le temps, ce est également constructible dans le temps.) Maintenant, le résultat souhaité produit un tel que . Afin d'éviter d'améliorer le théorème de la hiérarchie des meilleurs temps actuels, nous aurions besoin à la fois de $g(n)$ $f(n) / \log(f(n))$ $g(n) = f(n) / (\log f(n))^{3/2}$ $g$ $f$ $f$ $g$ $h$ $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$ $g(n) = o( h(n) / \log(h(n)) )$ et . Ces deux ensemble impliquent que . Puisque , nous avons , ou de manière équivalente . Mais , qui n'est pas . $h(n) = o(f(n) / \log(f(n))$ $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$ $h(n) \geq g(n)$ $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$ $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$ $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))}$ $o(f(n) / \log(f(n))$

Joshua Grochow
la source

Cool! Notez également qu'il existe un meilleur théorème de hiérarchie temporelle si le nombre de bandes est fixe. Voir "La stricte hiérarchie déterministe du temps" par Martin Furer.

Michael Wehar

@MichaelWehar: Merci pour le pointeur! En effet, lorsque l'on devient si serré qu'il ne nécessite que , comme le montre Furer lorsque le nombre de bandes est fixe, mon argument s'éloigne. (Et pour la même raison, mon argument disparaît si cette question concernait la hiérarchie spatiale au lieu du temps: pour l'espace, nous avons un théorème de hiérarchie parfaitement serré même si # les bandes ne sont pas corrigées.)

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

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

Joshua Grochow

Je pense qu'un tel comportement est vrai pour les DTM 1 bande. D'une part, nous avons . Malheureusement, la seule référence que je connaisse est en allemand: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8. $\mathrm{DTIME}_1(O(n)) = \mathrm{DTIME}_1(o(n \log n))$

En revanche, il devrait être possible de séparer et par la langue utilisant un argument de séquence de croisement standard. $\mathrm{DTIME}_1(O(n))$ $\mathrm{DTIME}_1(O(n \log n))$ $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^* \}$

Markus Bläser
la source