Zeitkomplexität mit irrationalem Exponenten?

Gibt es ein natürliches Problem in P, für das die bekannteste gebundene Laufzeit die Form , wobei eine irrationale Konstante ist? $O(n^\alpha)$ $\alpha$

cc.complexity-theory time-complexity polynomial-time Andras Farago
quelle

Gute Frage! :)

Michael Wehar

siehe auch goldener Schnitt oder

in der Laufzeit

π

$\pi$ . Dies könnte möglicherweise eine große Liste sein ...

vzn

Ein Multiset zu sortieren liegt bei nH + n. Wenn Sie also H (Entropie) dazu bringen könnten, zu

zu konvergieren , wäre dies technisch gesehen eine Qualifikation. Das würde ich aber nicht "natürlich" nennen. Es könnte jedoch ein natürlicheres Problem geben, bei dem die Eingabe auf diese Weise reduziert wird.

n^{α - 1}

$n^{\alpha-1}$

KWillets

Zwar habe ich die Analyse nicht durchgeführt, und dies ist nicht unbedingt ein Entscheidungsproblem. Ich bin jedoch bereit, die bekanntesten Matrixmultiplikationsalgorithmen (von Coppersmith, Winograd, Stothers, Williams ua) mit irrationalem Exponenten einzusetzen.

Dies ist am einfachen Fall des Strassenschen Algorithmus mit der Laufzeit . $O(n^{\log_2 7})$

Und genau das haben Sie nicht gefragt, aber Ryan Williams hat gezeigt, dass alle Algorithmen, die SAT im Raum lösen, die Zeit benötigen , was ebenfalls interessant und ungewöhnlich ist Auftreten einer irrationalen Konstante in TCS. $n^{o(1)}$ $n^{2 \cos(\pi/7) - o(1)}$

Joe Bebel
quelle

Algorithmen jenseits von Strassens Algorithmus laufen nicht wirklich in

für ihren angegebenen Exponenten

. Vielmehr laufen sie für jedes

. Dies ist auf mehrere Grenzen zurückzuführen, die mit der Erzielung von

O (n^{α})

$O(n^\alpha)$

α

$\alpha$

ϵ > 0

$\epsilon > 0$

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

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

α

$\alpha$

Yuval Filmus

Die Zeitkomplexität von Strassen-Algorithmus ist wirklich ein Artefakt einer Master - Wiederholung

zur Lösung von

. Sie können viele Ihrer irrationalen Lieblingszahlen finden, indem Sie

und

mit unterschiedlichen Werten instanziieren .

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

Ja, ich stimme beiden zu. Ich nahm an, dass ich mit der Definition von P bereits locker war und nicht wirklich überprüft hatte, ob die Exponenten der Matrixmultiplikation irrational sind. Obwohl ich mich wundern würde, wenn sie rational wären, wenn man bedenkt, wie sie abgeleitet werden. Tief in der Tiefe spiegeln schnelle Matrixmultiplikationen noch immer die grundlegende Divisions- und Eroberungsmethode von Strassen wider, obwohl sie jetzt in der Tensorsprache beschrieben wird. Obwohl es einfach ist, Algorithmen zu konstruieren, wie Sie sie mit irrationalem

fällt mir neben der Multiplikation kein anderer natürlicher Divisions- und Eroberungsalgorithmus mit solchen Eigenschaften ein.

\log_{b} a

$\log_b a$

Joe Bebel

Einige ganzzahlige Multiplikationsalgorithmen haben irrationale Exponenten, wenn ich mich richtig erinnere.

Yuval Filmus

Richtig, wie bei Karatsuba. Aber es ist immer noch Multiplikation :)

Joe Bebel

Zeitkomplexität mit irrationalem Exponenten?

Antworten: