Bestimmt man, ob es in einem Intervall eine Primzahl gibt, von der bekannt ist, dass sie P- oder NP-vollständig ist?

Ich habe in diesem Beitrag über Stackoverflow gesehen, dass es einige relativ schnelle Algorithmen gibt, mit denen ein Intervall von Zahlen gesiebt werden kann, um festzustellen, ob es in diesem Intervall eine Primzahl gibt. Bedeutet dies jedoch, dass das Gesamtentscheidungsproblem von: (Gibt es in einem Intervall eine Primzahl?) Bei P liegt. (Es gab viele Antworten auf diesen Beitrag, die ich nicht gelesen habe. Ich entschuldige mich, wenn es sich um eine Frage handelt doppelt oder unnötig).

Wenn das Intervall groß genug ist (zum Beispiel ), dann gilt auf der einen Seite so etwas wie Bertrands Postulat und es gibt definitiv eine Primzahl in diesem Intervall. Ich weiß aber auch, dass es zwischen zwei Primzahlen beliebig große Lücken gibt (zum Beispiel . $[N,2N]$$[N!,N!+ N]$

Auch wenn das Entscheidungsproblem in PI liegt, kann nicht festgestellt werden, wie das entsprechende Suchproblem auch verfolgt werden kann, da wir möglicherweise nicht in der Lage sind, bei der Durchführung einer binären Suche auf dieselben Eigenschaften hinsichtlich der bekannten Verteilung von Primzahlen zurückzugreifen.

Ihr Problem ist also wie folgt:

Eingabe: Zahlen Frage: Gibt es eine Primzahl in [ l , u ] ?$\ell,u$
$[\ell,u]$

Soweit ich weiß, ist nicht bekannt, ob dieses Problem in P liegt oder nicht.

Folgendes weiß ich:

• Der Primitätstest (bei einer einzelnen Zahl wird geprüft, ob es sich um eine Primzahl handelt) erfolgt in P. Wenn der Bereich also klein genug ist, können Sie jede Zahl im Bereich ausführlich testen, um festzustellen, ob es sich um eine Primzahl handelt. Dies führt jedoch nicht zu a allgemeiner Algorithmus.

• Wenn Cramer Vermutung wahr ist, dann ist das Problem in Vermutung P. Cramer sagt , dass der Abstand zwischen aufeinanderfolgenden Primzahlen in der Nähe von ist O ( ( log n ) 2 ) , so dass der folgende Algorithmus in P sein wird: eine Iteration durch die Zahlen ℓ , ℓ + 1 , ℓ + 2 , ℓ + 3 , … , wobei jeweils geprüft wird, ob es sich um eine Primzahl handelt; Wenn Sie einen Prime finden, hören Sie sofort mit einer Ja-Antwort auf. Wenn Sie u drücken , hören Sie mit einer Nein-Antwort auf. Cramers Vermutung besagt, dass Sie nach den meisten O aufhören werden$n$$O((\log n)^2)$$\ell,\ell+1,\ell+2,\ell+3,\dots$$u$ Primalitätstests, damit der Algorithmus in polynomialer Zeit abläuft.$O((\log \ell)^2)$

  Leider scheinen die bekannten Ergebnisse zu den Hauptlücken nicht stark genug zu sein, um unbedingt zu beweisen, dass das Problem in P liegt.

• Hier ist ein weiterer einfacher Algorithmus: Wähle wiederholt eine zufällige ganze Zahl aus [ ℓ , u ] und teste, ob es eine Primzahl ist. Stoppen Sie, wenn Sie eine Primzahl finden oder wenn Sie jede Ganzzahl in [ ℓ , u ] ausprobiert haben und keine Primzahl war. Aus heuristischer Sicht sollten wir davon ausgehen, dass dies in der Praxis effizient ist. Der Primzahlsatz besagt, dass bei zufälliger Auswahl einer Zahl in der Nähe von u die Wahrscheinlichkeit, dass es sich um eine Primzahl handelt, bei etwa 1 / log n liegt . Aus heuristischen Gründen sollten wir erwarten, dass nach etwa 0 ( log u $r$$[\ell,u]$$[\ell,u]$$u$$1/\log n$$O(\log u)$Iterationen finden Sie in der Regel eine Primzahl und einen Stopp, falls vorhanden. Auf der anderen Seite werden Sie aufgrund des Problems des Couponsammlers nach etwa 0 ( ( u - l ) log ( u - l ) ) Iterationen anhalten , wenn es keine Primzahl im Bereich gibt . Wenn wir also eine gute Obergrenze für die Größe der längsten Lücke zwischen Primzahlen hätten, würde dies bedeuten, dass das Problem in BPP liegt. Auch ohne eine solche Obergrenze sind zufällige Probleminstanzen einfach.$[\ell,u]$$O((u-l) \log(u-l))$

• Wahrscheinlich kann man Siebmethoden anwenden, um die Laufzeit in der Praxis zu verbessern (z. B. um keine Primalitätstests für Zahlen durchzuführen, die durch eine kleine Primzahl teilbar sind). Ich weiß nicht, ob dies zu einer asymptotischen Besserung führen kann.

• Aufgrund dieser Techniken ist das Problem in der Praxis wahrscheinlich einfach.

• Aufgrund der obigen Ausführungen bezweifle ich persönlich, dass das Problem NP-vollständig ist.