Polytime- und Polyspace-Algorithmus zur Bestimmung des führenden Schnittpunkts von n diskreten monotonen Funktionen

Einige wichtige Aspekte: Ich bin ein Freizeitinformatiker und ein angestellter Software-Ingenieur. Also, entschuldigen Sie, wenn diese Aufforderung etwas außerhalb des linken Feldes zu liegen scheint - ich spiele routinemäßig mit mathematischen Simulationen und offenen Problemen, wenn ich nichts Besseres zu tun habe.

Während ich mit der Riemann-Hypothese spielte , stellte ich fest, dass die Primzahllücke auf der Grundlage des Schnittpunkts aller Komplementärfunktionen, die durch die Vielfachen jeder vorherigen Primzahl gebildet werden, auf eine Wiederholungsrelation reduziert werden kann (scharfe Beobachter werden feststellen, dass dies eine Verallgemeinerung von ist) das Sieb des Eratosthenes ). Wenn dies für Sie absolut keinen Sinn ergibt, machen Sie sich keine Sorgen - es ist immer noch Frontsache.$n-1$

Als ich sah, wie diese Funktionen zusammenhängen, wurde mir klar, dass die nächste Instanz jeder Primzahl auf den ersten Schnittpunkt dieser Funktionen reduziert werden kann, und zwar unendlich oft. Ich konnte jedoch nicht feststellen, ob dies in polytime und polyspace möglich ist. Also: Was ich suche, ist ein Algorithmus, der den ersten Schnittpunkt von diskreten (und gegebenenfalls monotonen) Funktionen in polynomialer Zeit und Raum bestimmen kann . Wenn derzeit kein solcher Algorithmus existiert oder existieren kann, ist ein knapper Beweis oder eine entsprechende Referenz ausreichend.$n$

Das nächste, was ich bisher finden kann, ist der Projektionsalgorithmus von Dykstra (ja, das ist RL Dykstra, nicht Edsger Dijkstra ), der sich meiner Meinung nach auf ein Problem der Ganzzahlprogrammierung reduziert und daher NP-schwer ist. In ähnlicher Weise müssen wir uns aufgrund der aktuellen schwachen Schranke von immer noch auf den exponentiellen Raum für unsere Wiederholung beschränken, wenn wir eine transitiv festgelegte Schnittmenge aller anwendbaren Punkte ausführen (wie sie derzeit als begrenzt verstanden werden$\ln(m)$ Primzahlen für jedes reelle (und damit e n Raum für jede Primzahl n ).$m$$e^n$$n$

Insgesamt frage ich mich, ob mein Verständnis der Reduzierung des Problems falsch ist. Ich erwarte nicht, dass die Riemannsche Hypothese (oder irgendein tiefes, offenes Problem in diesem Raum) bald gelöst wird. Ich versuche vielmehr, mehr darüber zu lernen, indem ich mit dem Problem spiele, und ich habe einen Haken in meiner Forschung getroffen.

Das Ermitteln, ob sich zwei als Programme angegebene monotone Funktionen überschneiden, ist nicht berechenbar. Ebenso ist die Bestimmung der ersten Kreuzung unter dem Versprechen, dass sie existiert, "willkürlich schwer" (definitiv nicht polytime).

$P$$f_P$$n$$1$$P$$n$$f_P$$1$$P$$P$$f_P$$1$

$T$$T$