Объясните параграф Википедии о тестировании на первичность
В теории вычислительной сложности формальный язык, соответствующий простым числам, обозначается как PRIMES. Легко показать, что PRIMES находится в Co-NP: его дополнение COMPOSITES находится в NP, потому что можно решить сложность, недетерминистически угадывая фактор.
В 1975 году Воган Пратт показал, что существует сертификат на первичность, который можно проверить за полиномиальное время, и, таким образом, PRIMES находится в NP, а, следовательно, в NP ∩ coNP. См. Сертификат первичности для деталей.
Последующее открытие алгоритмов Соловая – Штрассена и Миллера – Рабина привело PRIMES в coRP. В 1992 году алгоритм Адлемана – Хуанга [6] уменьшил сложность до ZPP = RP ∩ coRP, который заменил результат Пратта.
Тест примитивности Адлемана-Померанса-Румли от 1983 года поместил PRIMES в QP (квазиполиномиальное время), который, как известно, не сопоставим с классами, упомянутыми выше.
Из-за его практичности на практике, алгоритмов полиномиального времени, предполагающих гипотезу Римана, и других подобных доказательств, долгое время предполагалось, но не было доказано, что первичность может быть решена за полиномиальное время. Существование теста простоты AKS, наконец, решило этот давний вопрос и поместило PRIMES в P. Однако PRIMES, как известно, не является P-полным, и неизвестно, лежит ли он в классах, лежащих внутри P, таких как NC или L. Известно, что PRIMES не в AC0
Вопрос: Как долго предполагалось, что первичность является проблемой NP? когда он может легко проверить, является ли число простым или нет, проверяя его делимость на все числа от 1 до n.