Doppelte Exponentiale gegen einfache Exponentiale

Hier sind vier Grundsätze, die ich nicht vereinbaren kann:

Doppelte exponentielle Zeitalgorithmen laufen in der Zeit mit der Konstante $O(2^{2^{n^k}})$ $k \in \mathbb{N}$
Exponentielle Zeitalgorithmen laufen in mit einer Konstante von $O(2^{n^k})$ $k \in \mathbb{N}$
Die erstere Grenze wächst deutlich schneller als die letztere; Das heißt, es gibt Algorithmen, die in doppelter Exponentialzeit, aber nicht in Exponentialzeit ausgeführt werden
Wenn wir auf die doppelte Exponentialgrenze anwenden, haben wir , was innerhalb der zuvor angegebenen Exponentialgrenze liegt $a^{b^c} = a^{bc}$ $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$

Ich habe das Gefühl, dass mir eine gewisse Subtilität in Bezug auf die Definition eines Exponentialzeitalgorithmus fehlt, der eher in als in , aber ich bin mir nicht sicher, wo genau die Subtilität liegt. $O(2^{\mathrm{poly}(n)})$ $O(2^{n})$

asymptotics discrete-mathematics notation Badroit
quelle

Ich habe die Tags und Kacheln bearbeitet, da diese Frage eigentlich nichts mit Komplexitätstheorie zu tun hat: Es geht um mathematische Notation und das asymptotische Verhalten mathematischer Funktionen.

David Richerby

Antworten:

Das Problem beruht auf einer mehrdeutigen Terminologie.

, aber . Mit anderen Worten, Exponenten sind nicht assoziativ. $(a^b)^c = a^{bc}$ $a^{(b^c)} \neq a^{bc}$

Herkömmlicherweise werden verschachtelte Exponentiale ohne Klammern auf diese zweite Weise gruppiert, da dies nützlicher ist. Also . Wenn wir über sprechen wollten , könnten wir stattdessen einfach schreiben , also behalten wir uns die doppelte Exponentialschreibweise für den anderen Fall vor. $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$ $(2^2)^n$ $2^{2n}$

Draconis
quelle

Diese Konvention ist die einzig vernünftige. Wie Sie beschrieben haben, wäre die Wahl der anderen Art der Gruppierung nutzlos, da wir diesen Wert / diese Funktion bereits mit

anstelle eines ausgefallenen "doppelten Exponentials" ausdrücken könnten .

a^{b \cdot c}

$a^{b\cdot c}$

Bakuriu

@ Bakuriu Oh, in der Tat, obwohl es wichtig ist zu beachten, dass es nur eine Konvention ist. (Es könnte auch die Konvention geben, immer Klammern zu verwenden, was LaTeX tut: Es weigert sich zu erraten, wie man gruppiert a^b^c, und wirft stattdessen einen Fehler aus.)

Draconis

a^{b^{c}} = a^{(b^{c})}

$a^{b^c}=a^{(b^c)}$

@ DavidRicherby Natürlich ist jede Notation konventionell! Das heißt aber nicht, dass es nicht erwähnenswert ist. Es ist eine bewusste Entscheidung von Mathematikern, diese Notation zu verwenden: und es ist eine gute Wahl, weil sie Mehrdeutigkeiten beseitigt und nützlicher ist als die Alternative. Aber es ist immer noch eine Wahl, und nichts hindert Sie daran, sie anders zu definieren (außer die Leser zu verwirren, ohne wirklich zu gewinnen).

Draconis

@ Bakuriu Ich würde nicht so weit gehen zu sagen, dass dies die einzig sinnvolle Konvention ist, da es mir sehr vernünftig erscheint anzunehmen, dass alle Operationen von links nach rechts ausgewertet werden, es sei denn, es gibt Klammern. Das machen wir mit Addition und Subtraktion und was Kinder in der Grundschule mit "PEMDAS" lernen. Die Tatsache, dass die Potenzierung nicht der Konvention folgt, hat mich in der Vergangenheit gestolpert, und fast jeder, der zuerst davon erfährt.

6005

$a^{(b^c)}$ $(a^b)^c$ $2^{2^k}$ $2^{(2^k)}$ $(2^2)^k$

DW
quelle