Pour chaque fonction calculable

Pour chaque fonction calculable existe-t-il un problème qui peut être résolu au mieux en temps ou existe-t-il une fonction calculable telle que chaque problème qui peut être résolu dans peut également résolu en temps ?Θ ( f ( n ) ) f O ( f ( n ) ) o ( f ( n ) $f$$\Theta(f(n))$$f$$O(f(n))$$o(f(n))$

Cette question m'est venue à l'esprit hier. J'y pense depuis un petit moment maintenant, mais je ne peux pas le comprendre. Je ne sais pas vraiment comment je ferais pour google, alors je demande ici. Voici ce que j'ai trouvé:

Ma première pensée a été que la réponse est oui: pour chaque fonction calculable le problème "Sortie points" (ou créer une chaîne avec points ou autre) ne peut évidemment pas être résolu en temps. Il suffit donc de montrer qu'il peut être résolu en temps . Pas de problème, prenez simplement le pseudo code suivant:f ( n ) f ( n ) o ( f ( n ) ) O ( f ( n ) $f$$f(n)$$f(n)$$o(f(n))$$O(f(n))$

x = f(n)
for i from 1 to x:
    output(".")

Il est clair que cet algorithme résout le problème déclaré. Et son exécution est évidemment dans , donc le problème est résolu. C'était facile, non? Sauf que non, ce n'est pas parce qu'il faut tenir compte du coût de la première ligne. L'exécution de l'algorithme ci-dessus est uniquement dans si le temps nécessaire pour calculer est dans . Ce n'est clairement pas vrai pour toutes les fonctions ¹ .Θ ( f ( n ) ) f ( n ) O ( f ( n ) $\Theta(f(n))$$\Theta(f(n))$$f(n)$$O(f(n))$

Cette approche ne m'a donc conduit nulle part. Je serais reconnaissant à tous ceux qui me pointent dans la bonne direction de comprendre cela correctement.

¹ Considérons par exemple la fonction . Clairement O ( p ( n ) ) = O ( 1 ) , mais il n'y a pas d'algorithme qui calcule p en temps O ( 1 ) .$p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$$O(p(n)) = O(1)$$p$$O(1)$

Par le théorème de Gap (en utilisant la formulation d' ici , cherchez 'gap'), pour toute fonction calculable non bornée , il existe une fonction calculable croissante (en fait, arbitrairement grande) f : N → N telle que D T I M E ( f ( n ) ) = D T I M E ( g ( f ( n ) ) .$g : \mathbb{N} \rightarrow \mathbb{N}$$f : \mathbb{N} \rightarrow \mathbb{N}$$DTIME(f(n)) = DTIME(g(f(n))$

Cela répond à votre question en ce qu'il existe un tel (infiniment grand, en fait): pour chaque fonction calculable g telle que g = o ( n ) , il existe une fonction croissante f telle que tous les problèmes résolubles en O ( f ( n ) ) les temps sont également résolubles en O ( g ( f ( n ) ) = o ( f ( n ) ) temps. Notez que $f$$g$$g = o(n)$$f$$O(f(n))$$O(g(f(n)) = o(f(n))$$f$ n'est pas nécessairement constructible dans le temps - pour le cas constructible dans le temps, voir la réponse de @RanG.

Dans la formulation de Wikipédia (qui nécessite que ), alors g becomes f devient votre exemple, et f doit être ω ( n ) (donc vous allez dans l'autre sens - 'problèmes résolubles en O ( g ( f ( n ) ) sont également résolubles en O ( g ( n ) ) 'est la partie intéressante).$g(x) \geq x$$g \circ f$$f$$\omega(n)$$O(g(f(n))$$O(g(n))$

L'article de Wikipédia ne note pas que augmente et peut en fait être arbitrairement grand ( f ( n ) ≥ g ( n ) par exemple). L'article qui prouve le théorème de l' écart ne mentionne et le prouvent (voir ici , par exemple).$f$$f(n) \geq g(n)$

Pour chaque fonction calculable existe-t-il un problème qui peut être résolu au mieux en temps Θ ( f ( n ) ) ou existe-t-il une fonction calculable f telle que tout problème pouvant être résolu dans O ( f ( n ) ) peut également être résolu en o ( f ( n ) ) temps?$f$$\Theta(f(n))$$f$$O(f(n))$$o(f(n))$

Si est une fonction constructible dans le temps , alors le théorème de la hiérarchie temporelle dit qu'il y a des problèmes qui nécessitent du temps O ( f ( n ) ) , et ne peuvent pas être résolus avec le temps o ( f ( n $f$$O(f(n))$. Plus précisément, DTIME(o(f(n$o\left (\frac{f(n)}{\log(f(n))}\right )$

Cela ne prend en compte que les problèmes de décision et ne tient pas compte du temps nécessaire pour générer la sortie.

J'essaierai de fournir quelque chose d'un cadre dans l'espoir qu'il donne une vision plus approfondie.

Lorsque vous arrivez à quelque chose d'aussi fondamental, il y a des pièges inattendus partout. Par exemple: qu'est-ce que "résoudre" un problème? Souvent en informatique, nous ne considérons que la variante "décision", dans laquelle nous recevons une entrée et n'avons besoin que de sortir Vrai ou Faux. Vous vous concentrez sur le problème de la "fonction".

Si vous considérez la notation O (f (n)) comme essayant de capturer la quantité de "travail" nécessaire pour résoudre un problème, utiliser la décision au lieu de la fonction (où la sortie est requise) semble préférable parce que vous séparez proprement le calcul de la mise en forme de la sortie .

Je ne pense pas que cela répondra à votre question, mais cela pourrait vous intéresser: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

Faites également attention au théorème d'accélération .