A hipótese de Riemann, com mais de um século e meio de idade, tem implicações profundas na matemática e agora um grande edifício da teoria matemática é provado condicionalmente, além de inúmeras variantes. Recentemente, deparei com uma referência a um resultado condicional no TCS com base na hipótese de Riemann. Estou, portanto, me perguntando,
Quais são as principais implicações da hipótese de Riemann no TCS?
Para começar, aqui está um exemplo de um artigo recente: Polinômios de Homomorfismo concluídos para VP por Durand, Mahajan, Malod, Rugy-Altherre e Saurab. Da introdução do artigo:
Uma das questões abertas mais importantes na teoria da complexidade algébrica é decidir se as classes VP e VNP são distintas. Essas classes, definidas pela primeira vez por Valiant em [13, 12], são os análogos algébricos das classes de complexidade booleana P e NP, e sua separação é essencial para separar P de NP (pelo menos de maneira não uniforme e assumindo a hipótese de Riemann generalizada, sobre o campo , [3]).
Respostas:
Primeiro, não conheço nenhuma aplicação de CS da hipótese de Riemann como tal. Existem várias aplicações de generalizações de RH.
Segundo, uma nota terminológica: ao contrário da crença popular, não existe "a hipótese generalizada de Riemann" ou "a hipótese extensa de Riemann". Ambos os termos são usados mais ou menos de forma intercambiável na literatura como uma denotação solta de qualquer tipo de generalização da UR para alguma classe de funçõesEles não têm significado específico fixo, ou pelo menos nenhum consistente entre trabalhos de autores diferentes (ou mesmo trabalhos diferentes do mesmo autor).L
O resultado mencionado no OP baseia-se no resultado de Koiran de que a teoria existencial de (que geralmente se chama "Nullstellensatz" de Hilbert) está em AM e, portanto, na hierarquia polinomial. Ele assume o RH para funções Dedekind ; especificamente, ele se baseia em uma versão eficaz do teorema da densidade de Chebotarev. ζC ζ
Outra classe de aplicativos de CS explora o fato de que todo caractere quadrático não trivial do Dirichlet modulo assume para alguns , originalmente devido a Ankeny, muitas vezes declarado com uma referência a Bach, que melhorou a constante na anotaçãoEle se baseia no RH para funções de caracteres quadráticos de Dirichlet, que é mais fraco que o das funções Dedekind . (Na verdade, o resultado é mais genérico para os caracteres Hecke de ordem finita e, em geral, é necessário o RH para as funções dos ditos caracteres Hecke, o que é de fato equivalente ao RH para Dedekindχ ( x ) = - 1 x = O ( ( log m ) 2 ) O L ζ L ζm χ(x)=−1 x=O((logm)2) O L ζ L ζ -funções. No entanto, os aplicativos de CS de que estou ciente não precisam disso.) As conseqüências são que se pode derandomizar vários algoritmos, como o algoritmo de teste de primalidade de Miller-Rabin ou o algoritmo de Shanks-Tonelli para calcular os primos de raiz quadrada do módulo.
Até onde eu sei, a UR não é útil para encontrar deterministicamente números primos em um determinado intervalo, conforme mencionado no comentário acima. Isso se seguiria da conjectura de Cramér ou de um limite semelhante em intervalos primos, mas a UR é fraca demais para provar tais limites (o termo de erro no teorema do número primo é pelo menos da ordem aproximadamente não importa o que).x−−√
fonte
Supondo uma hipótese extensa de Riemann, LM Adleman e HW Lenstra forneceram um algoritmo de tempo polinomial para encontrar um polinômio irredutível de um grau desejado em um campo finito: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art .pdf
fonte