Merlin pode convencer Arthur sobre uma certa quantia?

Merlin, que possui recursos computacionais ilimitados, quer convencer Arthur de que para com e O cálculo dessa soma da maneira direta (exponenciação e adição modular) leva tempo com multiplicação baseada em FFT. * Mas Arthur só pode executar operações .

m | \sum_{p \leq N, p prime} p^{k}

$m|\sum_{p\le N,\ p\text{ prime}}p^k$

(N, m, k)

$(N,m,k)$

k = O (\log N)

$k=O(\log N)$

m = O (N) .

$m=O(N).$

N (\log \log N)^{2 + o (1)}

$N(\log\log N)^{2+o(1)}$

O (N)

$O(N)$

(Notação, para compatibilidade com versões anteriores desta pergunta: Seja a soma igual a ; a questão é se é um número inteiro.) $m\alpha$ $\alpha$

Merlin pode convencer Arthur com uma sequência de comprimento ? Caso contrário, ele pode convencer Arthur com uma prova interativa (a comunicação total, é claro, deve ser )? Nesse caso, Merlin poderia usar uma sequência de comprimento ? Arthur poderia usar tempo? $O(N)$ $O(N)$ $o(N)$ $o(N)$

Arthur não tem acesso ao não-determinismo ou outras ferramentas especiais (métodos quânticos, oráculos que não sejam Merlin, etc.), mas possui espaço , se necessário. É claro que Arthur não precisa calcular a soma diretamente, ele apenas precisa estar convencido de que um dado triplo (N, m, k) torna a equação verdadeira ou falsa. $O(N)$

Observe que com é possível calcular a soma no tempo usando o método Lagarias-Odlyzko . Para a soma é superlinear e, portanto, não pode ser armazenada diretamente (sem, por exemplo, redução modular), mas não está claro se existe um algoritmo rápido. $k=0$ $O(N^{1/2+\varepsilon})$ $k>0$

Eu também estaria interessado em qualquer algoritmo para calcular a soma (modular ou não), além da alimentação direta e adição.

* números para calcular, tempo para cada cálculo. $N/\log N$ $\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

cc.complexity-theory ds.algorithms time-complexity interactive-proofs nt.number-theory Charles
fonte

Pós relacionada no Math.SE .

Hsien-Chih Chang

Sim, relacionado. A principal diferença é que a questão math.SE assume que Merlin possui zero recursos computacionais e este assume que ele possui recursos ilimitados.

Charles

E quanto ao tempo necessário para o teste de primalidade?

quer

@ Charles: Não vejo essa escala para contar números primos. Você pode expiá-lo? Eu teria pensado que isso exigia uma escala superlinear. A peneira de Eratóstenes fornece um algoritmo .

\sqrt{N}

$\sqrt{N}$

O (N^{2})

$O(N^2)$

Joe Fitzsimons 21/03

O algoritmo é devido a Lagarias e Odlyzko. É descrito, por exemplo, dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf (E não é mas )

O (\sqrt{N})

$O(\sqrt N)$

\tilde{O} (\sqrt{N}) .

$\tilde{O}(\sqrt N).$

Charles

Respostas:

Estou publicando isso separadamente do meu caso especial anterior, porque acredito que é uma abordagem diferente para o problema e tem pouca relação com minha outra resposta. Pode não ser exatamente o que você está procurando, mas é simples e chega perto.

Existe uma prova que Arthur sempre aceitará quando a prova estiver correta, mas rejeitará com probabilidade . Eis como funciona: Merlin envia a Arthur o par para cada . Arthur verifica a soma (considerando o tempo ). Arthur os controlos que o número correcto de números primos foi fornecido (por cálculo ), que é sublinear em . Por fim, para pares aleatórios , ele confirma que é primo e que . Isso leva tempo $\frac{1}{(\log \log N)^{2+o(1)}}$ $(p_i,c_i = p_i^k\mbox{ mod }m)$ $p\leq N$ $O(N/\log(N)) \times O(\log(N)) = O(N)$ $\pi(N)$ $N$ $S N$ $p$ $p_i^k \equiv c_i \mbox{ mod }m$ $SN~O((\log \log N)^{2+o(1)})$ . Tomando , obtemos uma escala de tempo linear. Assim, uma fração de todos os pares é verificada. Se alguma dessas falhas falhar, Arthur obviamente rejeitará. Para que Arthur aceite uma prova incorreta, deve haver pelo menos um par que falhe em um desses dois testes (ou o número de pares deve ser menor que que foi verificado anteriormente). Assim como uma fracção de todos os pares são verificados, o teste falhará para uma prova incorrecto com probabilidade de, pelo menos, . $S = (\log \log N)^{-(2+o(1))}$ $S$ $\pi(N)$ $S$ $S$

Observe que, para grande, isso é muito melhor do que suposições aleatórias, que sucedem com a probabilidade . $N$ $\frac{1}{m} = \frac{1}{O(N)}$

Joe Fitzsimons
fonte

Se postar duas respostas for uma má prática, entre em contato e eu as fundirei. Deixei-os separados, pois o último veio até mim e é uma abordagem completamente diferente em comparação com a primeira resposta.

Joe Fitzsimons 21/03

tudo bem por mim. especialmente nas perguntas da CW, é comum ter várias respostas.

Suresh Venkat 21/03

@Suresh: Sim, eu sei, mas isso não é CW, e eu não quero parecer uma rep-prostituta.

Joe Fitzsimons 21/03

Resposta muito boa. Ele maximiza os dois recursos - a string de Merlin é e Arthur usa o tempo . Nitpick: verificar os números primos individualmente levará muito tempo para ser vinculado, mas é claro que Arthur pode gerar todos eles e compará-los com a lista de Merlin (exigindo que esteja em ordem).

Θ (N)

$\Theta(N)$

Θ (N)

$\Theta(N)$

Charles

@ JoeFitzsimons: tudo bem :). Se ambas as respostas merecem rep você vai ter o dobro de pontos :)

Suresh Venkat

Esta é uma resposta completa para o problema que não usa o Merlin.

Deléglise-Dusart-Roblot [1] fornece um algoritmo que determina o número de primos até que são congruentes a módulo no tempoUma modificação do algoritmo de Lagarias-Odlyzko [2] permite que o mesmo seja calculado no tempo $x$ $l$ $k,$ $O(x^{2/3}/\log^2x).$ $O(x^{1/2+o(1)}).$

Usando qualquer um dos algoritmos, encontre o número de primos em todas as classes de resíduos mod primos até que seu produto seja maior quePara cada primo leve o número total de primos em cada classe de resíduos vezes essa classe de resíduos à ésima potência; isso fornece o valor de $m.$ $q,$ $k$

\sum_{\overset{p \leq N}{p prime}} p^{k} (\mod q) .

$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\pmod q.$

Use o Teorema do Restante Chinês para determinar o valor da soma mod $2\cdot3\cdots\log m.$

Pelo teorema do número primo, o maior número primo necessário é então isso fornece a soma no tempo $(1+o(1))\log m,$ $O(N^{1/2+o(1)}).$

Referências

[1] Marc Deléglise, Pierre Dusart e Xavier-François Roblot, Contando primos em classes de resíduos , Mathematics of Computation 73 : 247 (2004), pp. 1565-1575. doi 10.1.1.100.779

[2] JC Lagarias e AM Odlyzko, Computação : Um método analítico $\pi(x)$ , Journal of Algorithms 8 (1987), pp. 173-191.

[3] Charles, responda no MathOverflow . (Sim, é a mesma pessoa. Consulte as outras respostas para abordagens diferentes.)

Charles
fonte

Esta não é uma resposta completa, mas um caso especial (para um valor maior de que você considera), que eu havia originalmente publicado como comentário. No caso em que (para algum número inteiro ), existe uma prova simples e a string de Merlin pode ter comprimento zero. $k$ $k=x \phi(m)$ $x$

Para fazer isso, Arthur simplesmente calcula . Isso pode ser feito fatorando (que pode ser feito no tempo sublinear em mesmo usando a divisão de teste). Uma vez que para todos os , e outro modo, se então temos , onde é o número de distintos divisores primos de . Como apontado na seção de comentários, pode ser calculado no tempo sublinear em $\phi(m)$ $m$ $N$ $p^{x \phi(m)} \equiv 0 \mbox{ mod } m$ $p|m$ $p^{x \phi(m)} \equiv 1 \mbox{ mod } m$ $k=x \phi(m)$ $\sum_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$ $y$ $m$ $\pi(N)$ $N$ e, portanto, essa soma pode ser calculada diretamente por Arthur.

Além disso, no caso especial de , a soma não pode ser igual a , como . $1<N<m$ $m\alpha$ $1<\pi(N)<m$

Joe Fitzsimons
fonte