Les fonctions à croissance plus lente que Ackermann inverse apparaissent-elles dans les limites d'exécution?

Certains algorithmes complexes ( union-find ) ont la fonction Ackermann inverse presque constante qui apparaît dans la complexité temporelle asymptotique, et sont optimales dans le pire des cas si le terme Ackermann inverse presque constant est ignoré.

Existe-t-il des exemples d'algorithmes connus avec des durées de fonctionnement qui impliquent des fonctions qui croissent fondamentalement plus lentement que Ackermann inverse (par exemple, des inverses de fonctions qui ne sont pas équivalentes à Ackermann sous des transformations polynomiales ou exponentielles, etc.), qui donnent le pire des cas le plus connu complexité pour résoudre le problème sous-jacent?

reference-request algorithm-analysis time-complexity runtime-analysis user2566092
la source

algorithmes temporels? Vous posez des questions sur un problème connu dont l'algorithme le plus connu est

? Vous devez d'abord trouver une fonction qui croît "fondamentalement plus vite" que

, comme TREE

, puis prendre son inverse, puis trouver un problème qui lui convient!

O (1)

$O(1)$

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

Pål GD

il existe des algorithmes artificiels construits à partir de la hiérarchie temporelle thm

vzn

@vzn: Tout

n'est pas constructible dans le temps (ce qui inclut

). Le théorème de la hiérarchie temporelle ne peut donc pas être utilisé ici.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

mdxn

@mdx heureux que quelqu'un l'ait signalé, juste pour vous tester. Oui, récemment, je pensais qu'il pourrait y avoir une généralisation de la hiérarchie temporelle thm pour les fonctions sub-

. mais de toute façon la limite

est due au fait qu'une MT constructible dans le temps doit lire toutes les entrées, mais disons-nous que ces autres algorithmes, par exemple avec une complexité temporelle Ackermann inverse, ne le font pas? avoir du mal à visualiser ça! sentir la question est plus sur l'existence de sous -

langues .... peut - il y avoir une sorte d'enquête ou quelque part .... description

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

VZN

@vzn: L'OP a vraiment besoin de clarifier le modèle de calcul auquel il pense.

doivent être définis sur des MT à accès aléatoire (ou équivalents). Lors de la spécification de notre mécanique, nous pourrions ajouter par inadvertance trop de puissance. C'est peut-être même dans la mesure où la notion de complexité de calcul n'est pas fructueuse. Dans les termes les plus élémentaires, il nous faudrait changer notre notion de complexité temporelle (ce que fait le temps d'exécution amorti) avec le risque qu'une telle définition devienne très artificielle (il en va de même pour le modèle de calcul).

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

mdxn

Réponses:

$O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$ lui-même.) Le problème de sensibilité demande de calculer, pour un graphe donné et un arbre couvrant minimum donné, par combien chaque poids de bord peut changer sans changer l'arbre couvrant minimum.

(Merci à Tsvi Kopelowitz pour cette référence.)

Yuval Filmus
la source

Je ne sais pas si Ackermann logarithme inverse est "fondamentalement plus lent" que Ackermann inverse, mais j'ai trouvé ce type de durée de fonctionnement surprenant.

Yuval Filmus

$\alpha^*(n)$ $n$

templatetypedef
la source

-1

Quand Alan Turing a découvert l'ordinateur, il y avait plusieurs modèles pour l'ordinateur proposé. Turing a prouvé que certains (3) de ces modèles pouvaient se simuler ET calculer la fonction Ackermann, tandis que les autres modèles pouvaient se simuler mais pas la fonction Ackermann (ils ne pouvaient donc pas simuler les 3). Par conséquent, ces 3 modèles (Turing Machine, von Neumann et un que je ne connais pas) ont été choisis comme architecture pour un ordinateur. Cela ne signifie pas que la fonction Ackermann est la limite de l'ordinateur, mais je suppose que c'est une science difficile. Je ne connais aucune fonction calculable qui se développe plus rapidement que la fonction Ackermann.

Maintenant, je ne pense pas qu'il y ait un problème pratique qui corresponde à votre question, mais peut-être pouvons-nous en construire un. Nous devons cependant imposer des contraintes à l'entrée. Comme nous ne pouvons pas utiliser O (n), nous ne pouvons pas vérifier l'ensemble de l'entrée. En fait, nous ne pouvons même pas vérifier la longueur de l'entrée car ce serait O (log n). Donc, nous avons besoin comme premier paramètre d'une représentation de la longueur du reste de l'entrée, par exemple c telle que Ackermann (c) soit la longueur de l'entrée. Comme cela ne convient pas non plus, nous demandons comme première valeur dans notre entrée le paramètre c, tel que bb (c) soit de la longueur de l'entrée, où bb est la fonction de castor occupé. Cette fonction est incomputable mais bb (c) existe certainement. Ensuite, l'algorithme se présente comme:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

Le but de l'algorithme est de vérifier que si c est l'inverse de bb, si alors la longueur d'entrée est supérieure à bb (c).

S'il y a une fonction calculable qui croît plus vite que la fonction Ackermann, je pense que nous pouvons utiliser son inverse pour créer un algorithme qui répond à votre question sur n'importe quelle entrée.

Albert Hendriks
la source

Il existe certainement des fonctions qui croissent plus rapidement que la fonction Ackermann comme indiqué dans les commentaires (TREE (n)). La partie délicate de la question consiste à construire un algorithme avec une limite d'exécution de l'inverse de cette fonction. Une telle machine n'a pas assez de temps pour calculer l'inverse de la fonction en premier lieu, donc la construction d'une MT qui y parvient n'est pas simple.

mdxn