Komplexität der Exponentialfunktion

Wir wissen, dass die Exponentialfunktion über natürliche Zahlen in der Polynomzeit nicht berechenbar ist, da die Größe der Ausgabe in der Größe der Eingaben nicht polynomiell begrenzt ist. $\exp(x,y) = x^y$

Ist dies der Hauptgrund für die Schwierigkeit, die Exponentialfunktion zu berechnen, oder ist die Exponentiation unabhängig von dieser Überlegung von Natur aus schwierig zu berechnen?

Wie komplex ist der Bitgraph der Exponentialfunktion?
${⟨ 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
quelle

Ich habe den Begriff "EXP" in "L" geändert, da EXP der Name einer berühmten Komplexitätsklasse ist und zu Verwirrung führen kann.

MS Dousti

Wenn

auf eine Potenz von 2 beschränkt ist, dann

ist

. Auch der Graph der Potenzierung

hat eine geringe Komplexität.

x

$x$

L

$L$

A C^{0}

$AC^0$

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

$\Gamma exp=\{(x,y,z) : x^y=z\}$

Kaveh

Sadeq: Wenn Sie Komplexitätsklassen vermeiden möchten, ist L in keiner Weise besser als EXP ... Änderte es auf X.

Peter

@Peter: In diesem Zusammenhang ist L mit Sicherheit eine "Sprache" und nicht die Komplexitätsklasse "Log-Space". Auf jeden Fall ist X eine viel bessere Wahl.

MS Dousti

@Kaveh: Die Frage besagt, dass es um die Exponentialfunktion der natürlichen Zahlen geht.

Tsuyoshi Ito

Antworten:

Hier sind einige Obergrenzen.

Durch wiederholtes Quadrieren liegt das Problem bei PSPACE.

Es gibt eine etwas bessere Obergrenze. Das Problem ist ein Sonderfall des BitSLP-Problems: Bei einem geradlinigen Programm, das mit 0 und 1 beginnt, mit Addition, Subtraktion und Multiplikation, die eine ganze Zahl N darstellen , und bei gegebenem i ∈ℕ wird entschieden, ob das i- te Bit (Zählen ab dem niedrigstwertiges Bit) der binären Darstellung von N ist 1. Das BitSLP-Problem befindet sich in der Zählhierarchie ( CH ) [ABKM09]. (Es wird angegeben , in [ABKM09] , dass nachgewiesen werden kann , dass das BitSLP Problem in PH ist ^{PP ^{PP ^{PP ^PP}}} .)

Die Mitgliedschaft in CH wird oft als Beweis dafür gewertet, dass das Problem wahrscheinlich nicht PSPACE-schwer ist, da die Gleichheit CH = PSPACE impliziert, dass die Zählhierarchie zusammenbricht. Ich weiß jedoch nicht, wie stark diese Beweise sind.

In Bezug auf die Härte wird gezeigt, dass BitSLP in demselben Artikel [ABKM09] # P-hart ist. Der dortige Beweis scheint jedoch keine Härte der Sprache X in der Frage zu implizieren .

Verweise

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen und Peter Bro Miltersen. Zur Komplexität der numerischen Analyse. SIAM Journal on Computing , 38 (5): 1987–2006, Januar 2009. http://dx.doi.org/10.1137/070697926

Tsuyoshi Ito
quelle

Keine vollständige, aber zumindest teilweise Antwort.

Ich stelle fest, dass die beiden bisher erschienenen Antworten nicht die Tatsache erwähnt haben, dass es einen -Algorithmus zur Berechnung des modularen Exponentials wobei die Anzahl der Bits in ist und ist der Exponent, der dem schnellsten Multiplikationsalgorithmus entspricht. Somit können die weniger signifikanten Bits des Exponentials effizient berechnet werden (in oder weniger). $O(n^{1+\omega})$ $x^y ~\mbox{mod }z$ $n$ $z$ $\omega$ $O(n^3)$

Der Weg, dies zu tun, ist ziemlich einfach: Sie können , , berechnen . Offensichtlich und so , aber da es nur ist Begriffe Dieser Vorgang dauert nur $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$ Multiplikationen.

Des Weiteren können wir schreiben als , so die höchstwertigen Bits entsprechen , welche etwa auch , da diese effizient berechnen können nur auf dem höchstwertigen Bit auf der abhängig von . $x^y$ $(\sum_{i=0}^n 2^i x_i)^y$ $2^{ny}$ $x$

So ist die einzige wirkliche Problem Begriffe werden durch die Bits in Richtung Zentrum von verursacht . $x^y$

Joe Fitzsimons
quelle

Es gibt eine interessante Beziehung zwischen dieser und meiner Antwort. Wenn ich mich nicht irre, besteht eine grobe Übersicht über den in meiner Antwort zitierten Algorithmus in [ABKM09 ] darin, diese Idee mit dem chinesischen Restsatz zu kombinieren, um höhere Bits zu erhalten.

Tsuyoshi Ito

Ah, das hatte ich nicht gemerkt.

Joe Fitzsimons

[Diese Antwort erklärt einige interessante Aspekte der Antwort von Per Vognsen . Es ist keine direkte Antwort auf die Frage des OP, kann jedoch bei der Lösung solcher Fragen hilfreich sein.]

$i$ Bit der irrationalen Zahl $\pi$ , ohne zuerst den ersten zu berechnen $i-1$ Bits. Der Artikel weist darauf hin, dass BPP-Formeln auch für andere irrationale Zahlen existieren.

Schauen Sie sich als nächstes Dick Liptons Einstellung zum Thema an: Cooks Klasse enthält Pi . Der Artikel beschreibt im Wesentlichen, dass die Entscheidung $i$ th bisschen von $\pi$ ist in der Klasse von Steve Cook ( $\rm SC$ , die in der Polynomzeit und im polylogarithmischen Raum akzeptierte Sprachklasse), und dass diese Tatsache außerordentlich seltsam ist, wie er es gegen "konventionelle Weisheit" nennt.

PS: Am Ende seines Artikels gibt Dick zu, dass der Algorithmus möglicherweise nicht mehr funktioniert $\rm SC$ Eine solche Möglichkeit ist jedoch jenseits des "praktischen Gebrauchs".

MS Dousti
quelle