Komplexitätstheoretisch schwierig, den Wert von

13

Die prime-Zählfunktion , degradiert , wird als die Anzahl der Primzahlen weniger definiert als oder gleich .π(x)x

Wir können ein Entscheidungsproblem aus wie folgt definieren:π(x)

Entscheide bei zwei binär geschriebenen Zahlen und , ob .xnπ(x)=n

Ein Freund und ich haben heute über dieses Problem gesprochen. Es gibt einen Pseudopolynomialzeit-Algorithmus für dieses Problem - zählen Sie einfach bis , und verwenden Sie bei jedem Schritt die Testdivision, um festzustellen, wie viele der Zahlen Primzahlen sind, und prüfen Sie, ob dies gleich . Das Problem liegt auch bei PSPACE, da der gerade beschriebene Algorithmus so implementiert werden kann, dass er nur den polynomiellen Hilfsraum verwendet.nxn

Ich habe jedoch Probleme, einen Weg zu finden, um dieses Problem in eine Klasse mit geringerer Komplexität einzuteilen. Ich kann nicht erkennen, wie ein Polynom-Zeit-Verifizierer für das Problem erstellt werden kann, daher bin ich nicht sicher, ob es sich um einen NP handelt, und mir fällt überhaupt keine Möglichkeit ein, ihn in die Polynom-Hierarchie aufzunehmen.

Was ist die am besten geeignete Komplexitätsklasse für dieses Problem?

Vielen Dank!

templatetypedef
quelle
in der Regel diese Art von Problemen auf der Riemannschen Vermutung hängen neigen .... gibt es viele „in der Nähe“ -Funktionen zu verkaufen , die diese Verbindung haben ....
VZN

Antworten:

11

Dies ist ein sehr offenes Problem. Ich werde einige Klassen skizzieren, in die das Problem "natürlich" passen könnte.

Es ist etwas umständlich, mit Ihrer Definition zu arbeiten, und es ist schwierig, das Problem in eine vorhandene Komplexitätsklasse zu integrieren. Die von Ihnen definierte Sprache ist der Schnittpunkt der Sprachen und { ( x , n ) | π ( x ) n } . Also, wenn zum Beispiel { ( x , n ) | π ( x ) n } war in der Klasse{(x,n)|π(x)n}{(x,n)|π(x)n}{(x,n)|π(x)n} dann { ( x , n ) | π ( x ) n } in wäre c o K . Dies erschwert die Charakterisierung der von Ihnen definierten Sprache, da man "den Schnittpunkt einer Sprache in K mit einer Sprache in c o K " angebenmüsste, um die engste Bindung zu erhalten.K{(x,n)|π(x)n}coKKcoK

Das Problem "Berechne " ist ein Problem in # P , wobei # P F P S P A C E die Klasse von Problemen der Form "Berechne die Anzahl von Akzeptanzpfaden eines nicht deterministischen Polynoms TM" ist. Offensichtlich können wir ein nicht deterministisches TM konstruieren, das eine Zahl q x errät , und dann (mit AKS) testen, ob q eine Primzahl ist.π(X)#P#PFPSPACEqxq

Eine Entscheidungsvariante von ist P P , was die Klasse von Sprachen ist, die die Form haben: "Akzeptieren bei einem nicht deterministischen Polynom TM mindestens die Hälfte der Berechnungspfade?". Beide { ( x , n ) | π ( x ) n } und { ( x , n ) | π ( x ) n } sind wahrscheinlich reduzierbar auf ein Problem in P P#PPP{(x,n)|π(x)n}{(x,n)|π(x)n}PP (indem Sie etwas an dem oben genannten TM herumfummeln, um die Anzahl der akzeptierenden Pfade auszugleichen).

Tom van der Zanden
quelle
3

Ihr Problem ist in C = P= Über den Algorithmus,

nicht deterministisch erraten eine ganze Zahl, so dass[m und ein bisschen0m<2log2(x+1)]b
wenn x < mdann ablehnen
wenn b=1dann:
wenn m < ndann akzeptieren sonst ablehnen
sonst:
Wenn m ist Primzahl, dann akzeptieren, sonst ablehnen

.


Insbesondere liegt Ihr Problem auch bei PP vor, da PP unter Wahrheitstabellenreduzierungen geschlossen ist .


quelle
2

In der Praxis erhalten Sie die Antwort möglicherweise schneller oder langsamer :-(

Es gibt einigermaßen gute Näherungen für π (x). Sie berechnen also eine solche Näherung, und wenn sie zu weit entfernt ist, wissen Sie, dass π (x) ≠ n ist. Wenn zum Beispiel n ≥ x ist, dann weiß ich, dass π (x) ≠ n ist, ohne etwas zu berechnen.

Es gibt einen schnellen Algorithmus, der bestimmt, ob π (x) gerade oder ungerade ist und in O (x ^ (1/2)) läuft. Sie können diesen Algorithmus ausführen und möglicherweise feststellen, dass die Parität von n falsch ist, und Sie sind fertig. Es hat eine Chance von fünfzig, wenn n eine zufällige ganze Zahl in der Nähe von π (x) ist.

Davon abgesehen kenne ich keine Methode, die schneller ist als die Berechnung von π (x). Was sehr unpraktisch ist - wenn ich ein Programm schreibe, das π (10 ^ 25) berechnen soll, und ein Ergebnis erhalte, das nicht offensichtlich falsch ist, gibt es keine Möglichkeit zu überprüfen, ob mein Ergebnis korrekt ist, außer das Wiederholen von Berechnung. Und Sie können die Berechnung nicht einfach mit meinem Programm wiederholen, Sie müssen ein anderes Programm schreiben, sonst würden Sie nicht feststellen, ob mein Programm Fehler enthält, die dazu führen, dass es eine etwas andere Funktion berechnet als π (x).

π (x) kann relativ einfach in etwa O (n ^ (2/3)) berechnet werden und ist mit einigen wirklich tiefen Rechnungen schneller.

gnasher729
quelle
1
Das ist interessant, aber die Frage bezieht sich eher auf die Komplexitätsklassen, die das Problem enthalten.
usul