Implikationen von Riemann-Hypothesenvarianten in TCS

Die über 1½ Jahre alte Riemann-Hypothese hat tiefgreifende Auswirkungen auf die Mathematik, und ein großes Gebäude der Mathematiktheorie wird nun unter Auflagen und zahlreichen Varianten bewiesen. Ich bin kürzlich auf einen Hinweis auf ein bedingtes Ergebnis in TCS gestoßen, das auf der Riemann-Hypothese basiert. Ich frage mich daher,

Was sind die wichtigsten Implikationen der Riemann-Hypothese in TCS?

Als Beispiel hier ein Beispiel aus einem kürzlich erschienenen Artikel, Homomorphism Polynomials complete for VP von Durand, Mahajan, Malod, de Rugy-Altherre und Saurab. Aus der Einleitung des Papiers:

Eine der wichtigsten offenen Fragen in der algebraischen Komplexitätstheorie ist die Entscheidung, ob die Klassen VP und VNP unterschiedlich sind. Diese Klassen, die zuerst von Valiant in [13, 12] definiert wurden, sind die algebraischen Analoga der booleschen Komplexitätsklassen P und NP, und ihre Trennung ist wesentlich für die Trennung von P von NP (zumindest ungleichmäßig und unter Annahme der verallgemeinerten Riemann-Hypothese). über dem Feld , [3]). $\mathbb{C}$

cc.complexity-theory algebraic-complexity arithmetic-circuits vzn
quelle

Bekannt ist, dass die verallgemeinerte relative Luftfeuchtigkeit impliziert, dass wir den Miller-Rabin-Primalitätstest derandomisieren können. Aber ich weiß nicht, ob damit etwas Tieferes oder Weiteres zu tun hat.

Usul

Hmm, ich denke, es gibt auch einen Zusammenhang mit dem Problem, eine große Primzahl deterministisch schnell zu finden ( dh wenn

in binär gegeben ist, finde eine Primzahl größer als

). Hoffe, jemand kenntnisreich kann kommentieren.

n

$n$

n

$n$

Usul

@usul RH impliziert, dass es für alle großen

eine Primzahl in

, die einen etwas nicht trivialen deterministischen Algorithmus ergibt, aber sehr weit von dem entfernt ist, was wir wollen. Darüber hinaus wissen wir, wie man die gleiche Laufzeit ohne RH erreicht, siehe das Polymath-Projektpapier arxiv.org/abs/1009.3956 . Ich glaube, ein besserer deterministischer Algorithmus zum Finden von Primzahlen unter der Annahme einer relativen Luftfeuchtigkeit wäre ein signifikantes Ergebnis.

n

$n$

[n, n + n^{0.5 + o (1)}]

$[n, n + n^{0.5 + o(1)}]$

Sasho Nikolov

Eine Erweiterung von RH ergibt auch eine gute Obergrenze für die kleinste Primzahl in arithmetischen Verläufen (siehe z. B. Abschnitt 5.5.4 in shoup.net/ntb/ntb-v2.pdf ).

Alex Golovnev

Antworten:

Erstens ist mir keine CS-Anwendung der Riemannschen Hypothese als solche bekannt. Es gibt verschiedene Anwendungen von Verallgemeinerungen der relativen Luftfeuchtigkeit.

Zweitens eine terminologische Anmerkung: Entgegen der landläufigen Meinung gibt es keine „verallgemeinerte Riemann-Hypothese“ oder „erweiterte Riemann-Hypothese“. Diese beiden Begriffe werden in der Literatur mehr oder weniger austauschbar als lose Bezeichnung für jede Art von Verallgemeinerungen der relativen Luftfeuchtigkeit auf eine Klasse von . Sie haben keine feste spezifische Bedeutung oder zumindest keine, die für Artikel verschiedener Autoren (oder sogar für verschiedene Artikel desselben Autors) konsistent ist. $L$

$\mathbb C$ $\zeta$

$m$ $\chi(x)=-1$ $x=O((\log m)^2)$ $O$ $L$ $\zeta$ $L$ $\zeta$

$\sqrt x$

Emil Jeřábek
quelle

L

$L$

ζ

$\zeta$

@ François: Ich bin auch persönlich an diese Terminologie gewöhnt. Aber das ziemlich bekannte Buch von Bach und Shallit definiert es genau umgekehrt (was übrigens Bachs eigener Verwendung in seinem Artikel "Explicit bounds ..." widerspricht).

Emil Jeřábek

Ist FACTORING in PPA nicht eine interessante Implikation? arxiv.org/abs/1207.5220

Domotorp

Könnte sein. Dies ist ein Beispiel für "Die Konsequenzen sind, dass man mehrere Algorithmen wie ... derandomisieren kann" im vorletzten Absatz, und ich denke nicht, dass es notwendig ist, meine eigene Arbeit in der Antwort zu bewerben.

Emil Jeřábek

Unter der Annahme einer erweiterten Riemann-Hypothese gaben LM Adleman und HW Lenstra einen Polynom-Zeitalgorithmus an, um ein irreduzibles Polynom eines gewünschten Grades über ein endliches Feld zu finden: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art .pdf

Lin Bingkai
quelle