Implikationen von Riemann-Hypothesenvarianten in TCS

10

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]).C

vzn
quelle
3
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
1
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 n ). Hoffe, jemand kenntnisreich kann kommentieren. nn
Usul
1
@usul RH impliziert, dass es für alle großen eine Primzahl in [ n , n + n 0,5 + o ( 1 ) ] gibt , 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+n0.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:

15

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

Cζ

mχ(x)=1x=O((logm)2)OLζLζ

x

Emil Jeřábek
quelle
Lζ
@ 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
7

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