Имейте в виду, что я почти полный нуб в теории сложности.
Я читал о том, как AKS Primality показывает, что числа размера n могут быть простыми или составными за полиномиальное время. Учитывая это, означает ли это, что поиск всех простых чисел, меньших числа n, также выполним за полиномиальное время, и, следовательно, алгоритм работает в FP. Кроме того, означает ли это, что подсчет всех простых чисел, меньших n, не относится к #P?
Что ж. То, что aks говорит, что проверка простоты для числа n - это O (b ^ k), где b = log2 (n), а k - некоторое целое число. Итак, если ваши вопросы перечислены все простые числа от 1 до n также O (b ^ k). Тогда ответ тривиально отрицательный, потому что количество простых чисел меньше n равно O(n/logn). Поэтому вам потребуется O(n/log(n)) только для их перечисления. Если ваш вопрос заключается в том, существует ли k такое, что сложность перечисления всех простых чисел, меньших n, составляет O(n^k). Тогда ответ тривиально да, потому что самая тривиальная форма решета — это O (n ^ (1.5)). Если что-то неясно, пожалуйста, дайте мне знать
