Мерлин, имеющий неограниченные вычислительные ресурсы, хочет убедить Артура, что для с и Простое вычисление этой суммы (модульное возведение в степень и сложение) занимает время с умножением на основе БПФ. * Но Артур может выполнять только операций.

(Обозначение для совместимости с более ранними версиями этого вопроса: пусть сумма равна ; тогда возникает вопрос, является ли целым числом.)$m\alpha$$\alpha$

Может ли Мерлин убедить Артура с помощью нити длины ? Если нет, может ли он убедить Артура с помощью интерактивного доказательства (общее общение, конечно, должно быть )? Если так, может ли Мерлин использовать строку длины ? Может ли Артур использовать время ?$O(N)$$O(N)$$o(N)$$o(N)$

Артур не имеет доступа к недетерминизму или другим специальным инструментам (квантовым методам, оракулам, отличным от Мерлина и т. Д.), Но при необходимости имеет пространство . Конечно, Артуру не нужно вычислять сумму напрямую, ему просто нужно убедиться, что данная тройка (N, m, k) делает уравнение истинным или ложным.$O(N)$

Обратите внимание, что при можно вычислить сумму за время используя метод Лагариаса-Одлызко . При сумма является суперлинейной и поэтому не может быть сохранена напрямую (без, например, модульного сокращения), но неясно, существует ли быстрый алгоритм.O ( N 1 / 2 + ε$k=0$$O(N^{1/2+\varepsilon})$$k>0$

Я также был бы заинтересован в любом алгоритме для вычисления суммы (модульной или другой), кроме как путем прямого включения и сложения.

* чисел для расчета, время для каждого расчета.lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) $N/\log N$$\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

Я публикую это отдельно от моего предыдущего особого случая, потому что я считаю, что это другой подход к проблеме, и он мало связан с моим другим ответом. Это может быть не совсем то, что вы ищете, но это просто и близко.

Существует доказательство того, что Артур всегда примет правильное доказательство, но с вероятностью отклонит . Вот как это работает: Мерлин посылает Артур пару для каждого простого . Артур проверяет сумму (принимая время ). Артур проверяет , что правильное количество простых чисел было поставлено (путем вычисления ) , которая является сублинейна в . Наконец, для случайных пар он подтверждает, что простое число и что . Это занимает время (pi,ci=p k i  mod m)p≤NO(N/log(N))×O(log(N))=O(N)π(N)NSNpp k $\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$С Н О ( ( журнал журнал N ) 2 + O ( 1 ) ) S = ( лог - лог - Н ) - ( 2 + O ( 1 ) ) S π ( N ) S $p_i^k \equiv c_i \mbox{ mod }m$$SN~O((\log \log N)^{2+o(1)})$, Взяв , мы получим линейное масштабирование по времени. Таким образом, часть всех пар проверяется. Если что-то из этого не получится, Артур, конечно, откажется. Чтобы Артур принял неверное доказательство, должна быть хотя бы одна пара, которая не прошла один из этих двух тестов (или количество пар должно быть меньше, чем который был проверен ранее). Так как доля всех пар проверяются, тест проваливается для некорректного доказательства с вероятностью по крайней мере .$S = (\log \log N)^{-(2+o(1))}$$S$$\pi(N)$$S$$S$

Обратите внимание, что для больших это намного лучше, чем случайное угадывание, которое успешно выполняется с вероятностью .$N$$\frac{1}{m} = \frac{1}{O(N)}$

Это полный ответ на проблему, которая вообще не использует Merlin.

Делеглиз-Дюзар-Робло [1] дают алгоритм, который определяет число простых чисел до , которые совпадают с по модулю за времяМодификация алгоритма Лагариаса-Одлызко [2] позволяет вычислять то же самое за время$x$$l$$k,$$O(x^{2/3}/\log^2x).$$O(x^{1/2+o(1)}).$

Используя любой алгоритм, найдите число простых чисел во всех простых классах модовых простых чисел, пока их произведение не станет большеДля каждого простого числа возьмем общее число простых чисел в каждом классе вычетов, умноженное на этот класс вычетов, до степени; это дает значение $m.$$q,$$k$

Используйте китайскую теорему об чтобы определить значение суммы mod$2\cdot3\cdots\log m.$

По теореме о простых числах наибольшее необходимое простое число так что это дает сумму во времени$(1+o(1))\log m,$$O(N^{1/2+o(1)}).$

Рекомендации

[1] Марк Делеглиз, Пьер Дюзар и Ксавье-Франсуа Робло, Подсчет простых чисел в классах вычетов , Математика вычислений 73 : 247 (2004), с. 1565-1575. дои 10.1.1.100.779

[2] JC Lagarias и AM Odlyzko, Computing : аналитический метод$\pi(x)$ , Journal of Algorithms 8 (1987), pp. 173-191.

[3] Чарльз, ответь на MathOverflow . (Да, это один и тот же человек. См. Другие ответы там для различных подходов.)

Это не полный ответ, а особый случай (для большего значения чем вы считаете), который я первоначально разместил в качестве комментария. В случае, когда (для некоторого целого числа ), есть простое доказательство, и строка Мерлина может иметь нулевую длину.$k$$k=x \phi(m)$$x$

Для этого Артур просто вычисляет . Это можно сделать с помощью факторизации (которая может быть выполнена по времени, сублинейному по даже с использованием пробного деления). Поскольку для всех , а противном случае, если тогда мы имеем , где - число различных простые делители . Как указано в разделе комментариев, можно рассчитать по сублинейному времени в$\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$и, следовательно, эта сумма может быть непосредственно рассчитана Артуром.

Кроме того, для частного случая, когда сумма не может быть равна , так как .m α 1 < π ( N ) < $1<N<m$$m\alpha$$1<\pi(N)<m$