Complexité de la fonction exponentielle

Nous savons que la fonction exponentielle sur les nombres naturels n'est pas calculable en temps polynomial, car la taille de la sortie n'est pas polynomiale dans la taille des entrées. $\exp(x,y) = x^y$

Est-ce la raison principale de la difficulté de calculer la fonction exponentielle ou est-ce que l'exponentiation est en soi difficile à calculer indépendamment de cette considération?

Quelle est la complexité du graphe en bits de la fonction exponentielle?
${⟨ x, y, i ⟩ ∣ x, y, i \in N and the i -th bit of x^{y} is 1}$ $\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$

cc.complexity-theory nt.number-theory Peter
la source

J'ai remplacé la notion "EXP" par "L", car EXP est le nom d'une classe de complexité connue et peut prêter à confusion.

MS Dousti

x

$x$ est limité à une puissance de 2, alors

L

$L$ est

A C^{0}

$AC^0$ . Le graphique de l'exponentiation

Γ e x p = {(x, y, z) : x^{y} = z}

$\Gamma exp=\{(x,y,z) : x^y=z\}$ a également une faible complexité.

Kaveh

Sadeq: Si vous voulez éviter les classes de complexité, L n'est en aucun cas meilleur que EXP ... Changé en X.

Peter

@Peter: Dans le contexte, L est sûrement un "langage" plutôt que la classe de complexité Log-space. Quoi qu'il en soit, X est un bien meilleur choix.

MS Dousti

@Kaveh: La question dit qu'il s'agit de la fonction exponentielle sur les nombres naturels.

Tsuyoshi Ito

Réponses:

Voici quelques limites supérieures.

En répétant la quadrature, le problème est dans PSPACE.

La limite supérieure est légèrement meilleure. Le problème est un cas particulier du problème BitSLP: Soit un programme en ligne droite commençant par 0 et 1 avec addition, soustraction et multiplication représentant un entier N , et étant donné i ∈ℕ, décide si le i- ème bit (à compter de la le bit le moins significatif) de la représentation binaire de N est égal à 1. Le problème de BitSLP se trouve dans la hiérarchie de comptage ( CH ) [ABKM09]. (Il est indiqué dans [ABKM09] qu'il peut être démontré que le problème de BitSLP est dans PH ^{PP ^{PP ^{PP ^PP}}} .)

L'adhésion à CH est souvent considérée comme une preuve qu'il est peu probable que le problème pose problème à PSPACE, car l'égalité CH = PSPACE implique que la hiérarchie de comptage s'effondre. Cependant, je ne sais pas à quel point cette preuve est réputée être solide.

En ce qui concerne la dureté, BitSLP est # P-dur dans le même papier [ABKM09]. Cependant, la preuve ne semble impliquer aucune dureté du langage X dans la question.

Les références

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen et Peter Bro Miltersen. Sur la complexité de l'analyse numérique. SIAM Journal on Computing , 38 (5): 1987-2006, janvier 2009. http://dx.doi.org/10.1137/070697926

Tsuyoshi Ito
la source

Pas une réponse complète, mais au moins partielle.

Je remarque que les deux réponses apparues jusqu’à présent n’ont pas mentionné le fait qu’il existe un algorithme pour calculer l’exponentielle modulaire où est le nombre de bits dans et où est l'exposant correspondant à l'algorithme de multiplication le plus rapide. Ainsi, les bits les moins significatifs de l'exponentielle peuvent être calculés efficacement (en ou moins). $O(n^{1+\omega})$ $x^y ~\mbox{mod }z$ $n$ $z$ $\omega$ $O(n^3)$

La façon de procéder est assez simple: vous pouvez calculer , , . Clairement , et donc , mais comme il n'y a que termes cela prend seulement multiplications. $c_1 = x$ $c_2 = x^2 ~\mbox{mod }z$ $c_j = c_{j-1}^2 ~\mbox{mod }z$ $c_j = x^{2^j}~\mbox{mod }z$ $x^y \equiv \prod_j c_j^{y_j}~\mbox{mod }z$ $n$ $c_j$ $n$

De plus, nous pouvons écrire comme , de sorte que les bits les plus significatifs qui correspondent à environ peuvent également être calculés efficacement dépend du bit le plus significatif de . $x^y$ $(\sum_{i=0}^n 2^i x_i)^y$ $2^{ny}$ $x$

Ainsi, les seuls problèmes réels sont causés par des bits vers le centre de . $x^y$

Joe Fitzsimons
la source

Il existe une relation intéressante entre cette réponse et la mienne. Si je ne me trompe pas, un aperçu général de l'algorithme de [ABKM09 ] cité dans ma réponse est de combiner cette idée avec le théorème du reste chinois pour obtenir des bits plus élevés.

Tsuyoshi Ito

Ah, je n'avais pas compris cela.

Joe Fitzsimons

[Cette réponse explique certains aspects intéressants de la réponse de Per Vognsen . Ce n'est pas une réponse directe à la question du PO, mais cela peut aider à résoudre de telles questions.]

Tout d’abord, jetez un coup d’œil au lien suivant: formule Bailey-Borwein-Plouffe (ou simplement formule BBP). Il est un moyen de calcul de la ème bit du nombre irrationnel , sans d' abord calculer les premiers des bits. L'article souligne qu'il existe également des formules de type BPP pour d'autres nombres irrationnels. $i$ $\pi$ $i-1$

Ensuite, regardez le point de vue de Dick Lipton sur le sujet: Cook's Class contient Pi . L'article décrit essentiellement que la décision du ème bit est dans la classe de Steve Cook ( , la classe des langues acceptées dans le temps et en espace polynomial poly-logarithmique), et que ce fait est extraordinairement étrange, comme il l' appelle cela contre "la sagesse conventionnelle". $i$ $\pi$ $\rm SC$

PS: À la fin de son article, Dick admet que l’algorithme est peut-être en dehors de , mais une telle possibilité dépasse le cadre de son "utilisation pratique". $\rm SC$

MS Dousti
la source