Implikasi dari varian Hipotesis Riemann dalam TCS

Riemann Hypothesis berusia lebih dari 1½ abad memiliki implikasi yang mendalam dalam matematika dan bangunan besar teori matematika sekarang terbukti secara kondisional dan banyak varian. Baru-baru ini saya menemukan referensi untuk hasil bersyarat di TCS berdasarkan pada hipotesis Riemann. Karena itu saya bertanya-tanya,

apa implikasi utama hipotesis Riemann dalam TCS?

Sebagai permulaan di sini adalah contoh dari makalah baru-baru ini, Polinomial Homomorfisme lengkap untuk Wakil Presiden oleh Durand, Mahajan, Malod, de Rugy-Altherre, dan Saurab. Dari pengantar makalah:

Salah satu pertanyaan terbuka yang paling penting dalam teori kompleksitas aljabar adalah memutuskan apakah kelas VP dan VNP berbeda. Kelas-kelas ini, pertama kali didefinisikan oleh Valiant dalam [13, 12], adalah analog aljabar dari kelas kompleksitas Boolean P dan NP, dan memisahkan mereka sangat penting untuk memisahkan P dari NP (setidaknya tidak seragam dan dengan asumsi Hipotesis Riemann yang digeneralisasi, di atas bidang , [3]). $\mathbb{C}$

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

Yang terkenal adalah bahwa Kesehatan Reproduksi umum menyiratkan bahwa kita dapat derandomisasi uji primality Miller-Rabin. Tetapi saya tidak tahu apakah ada sesuatu yang lebih dalam atau lebih luas terkait dengan itu.

usul

n

$n$

n

$n$

n

$n$

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

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

Juga, perpanjangan dari RH memberikan batas atas yang baik pada prime prime dalam perkembangan aritmatika (lihat, misalnya, Bagian 5.5.4 di shoup.net/ntb/ntb-v2.pdf ).

Alex Golovnev

Jawaban:

Pertama, saya tidak mengetahui adanya aplikasi CS dari hipotesis Riemann. Ada berbagai aplikasi generalisasi Kesehatan Reproduksi.

$L$

$\mathbb C$ $\zeta$

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

$\sqrt x$

Emil Jeřábek
sumber

L

$L$

ζ

$\zeta$

@ François: Saya pribadi juga terbiasa dengan terminologi itu. Tetapi misalnya, buku yang cukup terkenal dari Bach dan Shallit mendefinisikannya dengan cara yang persis berlawanan (yang secara kebetulan bertentangan dengan penggunaan Bach sendiri dalam makalahnya "Batas eksplisit ...").

Emil Jeřábek

Bukankah FAKTOR dalam PPA merupakan implikasi yang menarik? arxiv.org/abs/1207.5220

domotorp

Mungkin. Ini adalah contoh dari "Konsekuensinya adalah seseorang dapat derandomisasi beberapa algoritma, seperti ..." dalam paragraf kedua dari belakang, dan saya tidak berpikir itu perlu untuk mengiklankan pekerjaan saya sendiri dalam jawabannya.

Emil Jeřábek

Dengan asumsi Hipotesis Riemann diperpanjang, LM Adleman dan HW Lenstra memberikan algoritma waktu polinomial untuk menemukan polinomial tak tereduksi dari gelar yang diinginkan di bidang terbatas: http://www.math.leidenuniv.nl/ ~ hwl/PUBLICATIONS/1986a/art .pdf

Lin Bingkai
sumber