Нахождение простого больше заданной границы

25

Является ли детерминированный алгоритм за полиномиальное время известным для следующей задачи:

Ввод: натуральное число (в двоичной кодировке)n

Выход: простое число .p>n

(Согласно списку открытых проблем Леонарда Адлемана, проблема была открыта в 1995 году.)

Винченцо
источник
1
+1: это напомнило мне, что соответствующая естественная проблема решения - это не тестирование на простоту (которое находится в ), а скорее следующая проблема: задано , есть ли простое число в интервале ? a < b [ a , b ]Pa<b[a,b]
Каве
@Kaveh: три пальца, указывая на меня, я думаю. Мы должны установить политику, запрещающую ответы в комментариях;)
Сянь-Чи Чанг 之 之

Ответы:

23

Текущий лучший безусловный результат дал Одлызко, который находит простое число за времени. Сильная гипотеза в проекте Polymath4 стремится разрешить, если это можно сделать за полиномиальное время, при разумных теоретико-числовых предположениях, таких как GRH.O ( N 1 / 2 + O ( 1 ) )p>NO(N1/2+o(1))

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

В настоящее время проект стремится ответить на следующий вопрос:

Учитывая число и интервал между и , отметьте время для некоторого если интервал содержит простое число.Н 2 Н O ( N 1 / 2 - с ) с > 0NN2NO(N1/2c)c>0

Пока у них есть стратегия, которая определяет соотношение числа простых чисел в интервале.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/

Конг хан
источник
14

Предполагая стандартную гипотезу в теории чисел, которая утверждает, что

Гипотеза Крэмера : пусть будет n-м простым числом. Тогда p n + 1 - p n = O ( log 2 p n ) .pnpn+1pn=O(log2pn)

У нас есть детерминированный полиномиальный алгоритм для задачи, просто запустив тест на простоту для каждого числа больше начиная с n + 1 . (Конечно, n должно быть достаточно большим; для малых n мы рассматривали отдельно.)nn+1nn

Но я не уверен, что это можно доказать безоговорочно.

Сянь-Чжи Чан 張顯 之
источник
1
Мне любопытно, как стандартная гипотеза Крамера. У меня сложилось впечатление, что шансы были против этого.
Конг Хань,
@ Конг: Я не очень знаком с этой гипотезой, и у меня сложилось впечатление, что у нас есть доказательства в численных результатах, а также в случайной модели. Есть ли признаки того, что гипотеза может быть ложной? Может быть, я должен заявить «сильный» вместо «стандартный».
Сянь-Чи Чанг 之 之
@ Hsien-Chih: Я очень мало знаю об этом (кроме некоторых слухов и интереса к проектам Polymath), но эта статья Грэнвилля, связанная с вики о гипотезе, кажется, предлагает следующее: dartmouth.edu/~ шанс / случайные новости / for_chance_news / Риман /…
Конг Хан
@ Конг: похоже на приятное чтение, через несколько дней я его прочту!
Сянь-Чи Чанг 之 之