Implikacje wariantów hipotezy Riemanna w TCS

Ponad ~ 1,5-letnia hipoteza Riemanna ma głębokie implikacje w matematyce, a duży gmach teorii matematycznej jest teraz warunkowo udowodniony i liczne warianty. Ostatnio natknąłem się na odniesienie do wyniku warunkowego w TCS opartego na hipotezie Riemanna. Zastanawiam się zatem

jakie są główne implikacje hipotezy Riemanna w TCS?

Na początek jest przykład z niedawnej pracy Homomorphism Polynomials dla VP autorstwa Duranda, Mahajana, Maloda, de Rugy-Altherre i Saurab. Ze wstępu do artykułu:

Jednym z najważniejszych pytań otwartych w teorii złożoności algebraicznej jest decyzja, czy klasy VP i VNP są odrębne. Klasy te, po raz pierwszy zdefiniowane przez Valianta w [13, 12], są algebraicznymi analogami boolowskich klas złożoności P i NP, a ich oddzielenie jest niezbędne do oddzielenia P od NP (przynajmniej nierównomiernie i przy założeniu uogólnionej hipotezy Riemanna, nad polem , [3]). $\mathbb{C}$

cc.complexity-theory algebraic-complexity arithmetic-circuits vzn
źródło

Dobrze wiadomo, że uogólniona RH sugeruje, że możemy derandomizować test pierwotności Millera-Rabina. Ale nie wiem, czy jest z tym coś głębszego lub szerszego.

usul

Hmm, myślę, że istnieje również związek z problemem deterministycznie szybkiego znalezienia dużej liczby pierwszej ( tj. Biorąc pod uwagę

w postaci binarnej, znajdź liczbę pierwszą większą niż

). Mam nadzieję, że ktoś kompetentny może komentować.

n

$n$

n

$n$

usul

@usul RH sugeruje, że dla wszystkich dużych

istnieje liczba pierwsza w

, co daje nieco nietrywialny algorytm deterministyczny, ale jest bardzo daleki od tego, czego chcemy. Co więcej, wiemy, jak osiągnąć ten sam czas działania bez RH, patrz dokument projektu polymath arxiv.org/abs/1009.3956 . Uważam, że lepszy algorytm deterministyczny do znajdowania liczb pierwszych przy założeniu, że RH byłby znaczącym rezultatem.

n

$n$

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

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

Sasho Nikolov

Ponadto rozszerzenie RH daje dobrą górną granicę najmniejszej liczby pierwszej w postępach arytmetycznych (patrz np. Sekcja 5.5.4 w shoup.net/ntb/ntb-v2.pdf ).

Alex Golovnev,

Odpowiedzi:

Po pierwsze, nie znam żadnego zastosowania CS jako hipotezy Riemanna jako takiego. Istnieją różne zastosowania uogólnień RH.

Po drugie, uwaga terminologiczna: wbrew powszechnemu przekonaniu nie ma czegoś takiego jak „uogólniona hipoteza Riemanna” lub „rozszerzona hipoteza Riemanna”. Oba te terminy są używane bardziej lub mniej zamiennie w literaturze jako luźny denotacją jakiejkolwiek uogólnienia RH do pewnej klasy działanie funkcji. Nie mają ustalonego konkretnego znaczenia, a przynajmniej nie są spójne w pracach różnych autorów (a nawet różnych prac tego samego autora). $L$

Wynik wspomniany w OP opiera się na wyniku Koirana, że egzystencjalna teoria (która często przyjmuje mylącą nazwę „Nullstellensatz Hilberta”) jest w AM, a zatem w hierarchii wielomianowej. Zakłada RH dla funkcji Dedekinda ; w szczególności opiera się na skutecznej wersji twierdzenia o gęstości Czebotarewa. $\mathbb C$ $\zeta$

Inna klasa aplikacji CS wykorzystuje fakt, że każdy nietrywialny kwadratowy moduł Dirichleta modulo przyjmuje dla niektórych , pierwotnie z powodu Ankeny, często stwierdzane w odniesieniu do Bacha, który poprawiono stałą w notacji. Opiera się na RH dla funkcji kwadratowych postaci Dirichleta, która jest słabsza niż dla Dedekinda $m$ $\chi(x)=-1$ $x=O((\log m)^2)$ $O$ $L$ $\zeta$ -Funkcje. (Wynik faktycznie dotyczy bardziej ogólnie znaków Hecke o skończonym rzędzie i ogólnie wymaga RH dla funkcji wspomnianych znaków Hecke, co w rzeczywistości jest równoważne RH dla funkcji Dedekind . Jednak aplikacje CS Wiem, że tego nie potrzebuję.) Konsekwencją jest to, że można derandomizować kilka algorytmów, takich jak algorytm testowania pierwotności Millera – Rabina lub algorytm Shanksa-Tonellego do obliczania liczb pierwszych modulowych pierwiastków kwadratowych. $L$ $\zeta$

O ile mi wiadomo, RH nie jest przydatne do deterministycznego znajdowania liczb pierwszych w danym przedziale, jak wspomniano w komentarzu powyżej. Wynikałoby to z przypuszczenia Craméra lub podobnej granicy pierwszych liczb, ale RH jest zbyt słaby, aby udowodnić takie granice (warunek błędu w twierdzeniu liczby pierwszej jest co najmniej z grubsza rzędu bez względu na wszystko). $\sqrt x$

Emil Jeřábek
źródło

Zgadzam się, że użycie GRH / ERH nie jest całkowicie spójne (i jest to faux-pas terminologiczny, aby „rozszerzyć” i „uogólnić” oznaczać różne konkretne rzeczy). Zawsze jednak uczono mnie, że GRH jest rozszerzeniem funkcji

związanych ze znakami Dirichleta i że ERH jest rozszerzeniem funkcji

pól liczbowych.

L

$L$

ζ

$\zeta$

François G. Dorais,

@ François: Jestem również osobiście przyzwyczajony do tej terminologii. Ale na przykład dość dobrze znana książka Bacha i Shallita definiuje ją w dokładnie odwrotny sposób (co zresztą zaprzecza własnemu użyciu Bacha w jego pracy „Explicit bounds ...”).

Emil Jeřábek,

Czy FACTORING w PPA nie jest interesującą implikacją? arxiv.org/abs/1207.5220

domotorp

Może. Jest to przykład „Konsekwencją jest to, że można odandomizować kilka algorytmów, takich jak ...” w przedostatnim akapicie, i nie uważam za konieczne reklamowania własnej pracy w odpowiedzi.

Emil Jeřábek

Zakładając rozszerzoną hipotezę Riemanna, LM Adleman i HW Lenstra podali wielomianowy algorytm czasowy, aby znaleźć nieredukowalny wielomian o pożądanym stopniu w polu skończonym: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art .pdf

Lin Bingkai
źródło