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