Zeitkomplexität mit irrationalem Exponenten?

21

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

Andras Farago
quelle
4
Gute Frage! :)
Michael Wehar
1
siehe auch goldener Schnitt oder in der Laufzeitπ . 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
KWillets

Antworten:

22

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(nlog27)

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

Joe Bebel
quelle
3
Algorithmen jenseits von Strassens Algorithmus laufen nicht wirklich in für ihren angegebenen Exponenten α . Vielmehr laufen sie für jedes ϵ > 0 in O ϵ ( n α + ϵ ) . Dies ist auf mehrere Grenzen zurückzuführen, die mit der Erzielung von α verbunden sind . O(nα)αϵ>0Oϵ(nα+ϵ)α
Yuval Filmus
12
Die Zeitkomplexität von Strassen-Algorithmus ist wirklich ein Artefakt einer Master - Wiederholung zur Lösung von Θ ( n log b a ) . Sie können viele Ihrer irrationalen Lieblingszahlen finden, indem Sie a und b mit unterschiedlichen Werten instanziieren . T(n)=aT(n/b)+f(n)Θ(nlogba)ab
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. logba
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