Complexité temporelle avec exposant irrationnel?

Existe-t-il un problème naturel dans P pour lequel la limite de temps d'exécution la plus connue est de la forme , où est une constante irrationnelle ? $O(n^\alpha)$ $\alpha$

cc.complexity-theory time-complexity polynomial-time Andras Farago
la source

Bonne question! :)

Michael Wehar

voir aussi le nombre d' or ou

dans le temps d'exécution

π

$\pi$ . cela pourrait éventuellement être une grande liste ...

vzn

Le tri d'un multiset se fait autour de nH + n, donc si vous pouviez faire converger H (entropie) vers un certain

qui serait techniquement qualifié. Je n'appellerais pas cela "naturel". Cependant, il pourrait y avoir un problème plus naturel lorsque l'entrée est réduite de cette manière.

n^{α - 1}

$n^{\alpha-1}$

KWillets

Certes, je n'ai pas fait l'analyse, et ce n'est pas strictement un problème de décision, je suis prêt à parier que les algorithmes de multiplication matricielle les plus connus (par Coppersmith, Winograd, Stothers, Williams, et al) ont un exposant irrationnel.

Cela peut être vu plus clairement dans le cas simple de l'algorithme de Strassen, qui a le temps d'exécution . $O(n^{\log_2 7})$

Et ce n'est pas précisément ce que vous avez demandé, mais Ryan Williams a montré que tous les algorithmes qui résolvent SAT dans l'espace nécessitent un temps , ce qui est un autre intéressant et inhabituel apparition d'une constante irrationnelle dans TCS. $n^{o(1)}$ $n^{2 \cos(\pi/7) - o(1)}$

Joe Bebel
la source

Les algorithmes au-delà de l'algorithme de Strassen ne fonctionnent pas vraiment en

pour leur exposant déclaré

. Au contraire, pour chaque

ils fonctionnent dans

. Cela est dû à plusieurs limites impliquées dans l'obtention de

O (n^{α})

$O(n^\alpha)$

α

$\alpha$

ϵ > 0

$\epsilon > 0$

O_{ϵ} (n^{α + ϵ})

$O_\epsilon(n^{\alpha+\epsilon})$

α

$\alpha$

Yuval Filmus

La complexité temporelle de l'algorithme de Strassen est vraiment un artefact d'une récurrence maître

résolvant à

. Vous pouvez trouver plusieurs de vos nombres irrationnels préférés en instanciant

avec des valeurs différentes.

T (n) = a T (n / b) + f (n)

$T(n) = a T(n/b) + f(n)$

Θ (n^{\log_{b} a})

$\Theta(n^{\log_b a})$

a

$a$

b

$b$

Huck Bennett

Oui, je suis d'accord avec les deux. J'ai pensé que j'étais déjà lâche avec la définition de P, et que je n'avais pas vérifié si les exposants de multiplication de la matrice étaient irrationnels. Bien que je serais surpris s'ils étaient rationnels, compte tenu de la façon dont ils sont dérivés. Au fond, les multiplications matricielles rapides font toujours écho à la méthode de base de division et de conquête de Strassen, bien qu'elle soit maintenant décrite dans le langage tensoriel. En fait, bien qu'il soit facile de construire des algorithmes comme vous le décrivez avec un

irrationnel

, je ne peux penser à aucun autre algorithme naturel de division et de conquête avec une telle propriété, à part la multiplication.

\log_{b} a

$\log_b a$

Joe Bebel

Certains algorithmes de multiplication d'entiers ont des exposants irrationnels si je me souviens bien.

Yuval Filmus

À droite, comme celle de Karatsuba. Mais c'est toujours de la multiplication :)

Joe Bebel

Complexité temporelle avec exposant irrationnel?

Réponses: