Nachweis der (In-) Traktabilität dieser N-ten Hauptrezidivfolge

18

Wie aus meiner vorherigen Frage hervorgeht , habe ich mit der Riemannschen Hypothese als Frage der Freizeitmathematik gespielt. Dabei bin ich zu einer interessanten Wiederholung gekommen und bin gespannt auf seinen Namen, seine Verringerungen und seine Fähigkeit, die Lücke zwischen Primzahlen zu schließen.

Um genau zu sein, wir können die Lücke zwischen jeder Primzahl als eine Wiederholung der vorhergehenden Kandidatenprimzahlen definieren . Für unsere Basis von wäre zum Beispiel die nächste Primzahl:p0=2

p1=min{x>p0cos(2π(x+1)/p0)+1=0)}

Oder, wie wir sehen, indem wir dies zeichnen : .p1=3

Wir können den Prozess für Primzahlen wiederholen, indem wir jede Kandidat-Primzahl bewerten, die sich vorwärts wiederholt. Angenommen, wir möchten die nächste Primzahl . Unsere Kandidatenfunktion wird:p 2np2

p2=min{x>p1fp1(x)+((cos(2π(x+1)/p1)+1)(cos(2π(x+2)/p1)+1))=0}

Wo:

fp1(x)=cos(2π(x+1)/p0)+1 , wie oben.

Es ist leicht zu erkennen, dass jede Komponentenfunktion bei ganzzahligen Werten nur Null wird, und es ist ebenso leicht zu zeigen, wie dies unsere AND- und XOR-förmigen Beziehungen geschickt erfasst, indem die Eigenschaften der Addition und Multiplikation im Kontext eines trigonometrischen Systems ausgenutzt werden Gleichungen.

Die Wiederholung wird:

fp0=0p0=2fpn(x)=fpn1(x)+k=2pn1(cos(2π(x+k1)/pn1)+1)pn=min{x>pn1fpn(x)=0}

... wo das gesamte Problem davon abhängt, ob wir den Operator über diese Funktion in Polynomialzeit auswerten können . Dies ist im Endeffekt eine Verallgemeinerung des Siebs von Eratosthenes .min

Arbeitender Python-Code, um die Wiederholung zu demonstrieren:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

Ein kurzes Beispiel:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

Das Problem ist, dass ich jetzt sowohl als Mathematiker als auch als Informatiker über den Kopf komme. Insbesondere bin ich mit der Fourier-Analyse , der Definition von einheitlichen Deckungen oder der komplexen Ebene im Allgemeinen nicht kompetent , und ich bin besorgt, dass dieser Ansatz entweder völlig falsch ist oder einen lauernden Schrecken vor einem 3SAT-Problem verbirgt, das ihn in die Höhe treibt NP-Vollständigkeit.

Daher habe ich hier drei Fragen:

  1. Ist es angesichts meiner knappen Wiederholung oben möglich, die Position der Nullen in Zeit und Raum des Polynoms deterministisch zu berechnen oder zu schätzen?
  2. Wenn ja, oder wenn nicht, verbirgt es irgendwelche anderen Unterprobleme, die eine Polytime- oder Polyspace-Lösung unlösbar machen würden?
  3. Und wenn durch ein Wunder (1) und (2), welche dynamischen Programmierverbesserungen würden Sie machen, um diese Wiederholung von einem hohen Niveau aus zu erfüllen? Es ist klar, dass die Iteration derselben ganzen Zahlen durch mehrere Funktionen unelegant und ziemlich verschwenderisch ist.
MrGomez
quelle
Und für diejenigen, die trotz meiner Textwand immer noch hier sind: Ich bin mir nicht sicher, ob sich dies auf das Riemannsche Zeta reduziert, wodurch es die gleiche Komplexität erhält. Das glaube ich aber nicht.
MrGomez
1
1) Welche Tags möchten Sie? Sie können sie selbst erstellen, indem Sie sie nur verwenden. 2) Geben Sie eine allgemeine Definition für , dh was ist ? 3) Wenn Sie nach etwa einer Woche keine Antwort erhalten, möchten Sie sie möglicherweise so verschieben. f ( p n )ff(pn)
Raphael
1
Ich verfolge nicht alles in Ihrem Beitrag. Ich denke du meinst NP-komplett, nicht NP. Allgemein zu beweisen, dass eine zahlentheoretische Funktion NP-vollständig ist, ist eine ziemlich schwierige Aufgabe, da ihnen häufig jegliche kombinatorische Struktur fehlt / verbirgt, die es uns ermöglichen würde, Geräte für die Reduktion zu entwerfen.
Kaveh
1
Revision abgeschlossen. Es gibt sicherlich noch andere lauernde Probleme, aber meine ursprüngliche Darstellung war völlig daneben. Ich sollte mich mit meinem 24 Stunden jüngeren Ich beraten und ihn über die richtigen Definitionen von . Auf jeden Fall vielen Dank für Ihre Geduld und Ihre bisherigen Änderungen. Die aktuellen Tags sind jetzt auch zu meiner Zufriedenheit. :)f(x)
MrGomez
Ist es in Bezug auf nicht ausreichend, alle kleineren Primzahlen im Gegensatz zu allen kleineren Zahlen zu "überprüfen"? f
Raphael

Antworten:

1

Das folgende Papier zeigt, dass PRIMES in P ist (es wurde auch 2006 mit einem Gödel-Preis ausgezeichnet):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Wenn Sie die Lösung der N-ten Prim-Minimierungsprozedur auf den AKS-PRIMES-Algorithmus setzen (Modulo-A-Subtraktion), erhalten Sie möglicherweise eine nachvollziehbare Lösung für die Wiederholungsrelation (wenn Sie nachweisen können, dass die Primlücke durch die Wiederholungsrelation gegeben ist).

Quellcodes finden Sie im Internet. Ich zeige hier nicht auf sie, weil ich sie nicht persönlich überprüft habe.

Möglicherweise haben wir jedoch noch die Obergrenze von um alle Zahlen zu überprüfen ...n

user13675
quelle
1
Die Rosettacode-Seite ist völlig falsch benannt. Dies ist nicht der AKS-Primalitätstest und ist eine Wiederholung der Versuchsteilung durch alle ganzen Zahlen kleiner als n. Andererseits lohnt es sich, zu bemerken, dass die Ursprünglichkeit in P liegt, und zu prüfen, ob dies Licht auf die ursprüngliche Frage wirft.
DanaJ
Guter Punkt ... Ich werde das beheben ...
user13675
1
Primzahlen in P implizieren nicht, dass wir in der Polynomzeit deterministisch Primzahlen erzeugen können. Es ist ein hartes offenes Problem. ( ist eine Exponentialfunktion in der Größe der Eingabe, die .) lgnnlgn
Kaveh