Znalezienie liczby pierwszej większej niż podana granica

Jest deterministycznym algorytmem czasu wielomianowego znanym z następującego problemu:

Dane wejściowe: liczba naturalna (w kodowaniu binarnym) $n$

Wyjście: liczba pierwsza . $p > n$

(Według listy otwartych problemów Leonarda Adlemana problem był otwarty w 1995 r.)

— Vincenzo
źródło

+1: Przypomniało mi, że odpowiadającym mu problemem naturalnej decyzji nie jest testowanie pierwotności (co jest w ), ale raczej następujący problem: biorąc uwagę , czy istnieje liczba pierwsza w przedziale ?

P

$\mathbf{P}$

a < b

$a<b$

[a, b]

$[a,b]$

— Kaveh

@Kaveh: Chyba trzy palce skierowane w moją stronę. Powinniśmy ustalić politykę zabraniającą odpowiedzi w komentarzach;)

— Hsien-Chih Chang 張顯之

Odpowiedzi:

Obecny najlepiej bezwarunkowy wynik podaje Odlyzko, która znajduje się doskonałą w razem. Silna hipoteza projektu Polymath4 ma na celu rozstrzygnięcie, czy można tego dokonać w czasie wielomianowym, przy rozsądnych założeniach teoretycznych, takich jak GRH. $p >N$ $O(N^{1/2 + o(1)})$

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

Obecnie projekt stara się odpowiedzieć na następujące pytanie:

Biorąc pod uwagę liczbę oraz odstęp pomiędzy a , sprawdzenie w czasie od pewnego , jeżeli przedział zawiera pierwszą. $N$ $N$ $2N$ $O(N^{1/2 - c})$ $c>0$

Jak dotąd mają strategię, która określa parzystość liczby liczb pierwszych w przedziale.

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

— Cong Han
źródło

Zakładając standardowe przypuszczenie w teorii liczb, które to stwierdza

Cramera przypuszczenie : Niech jest n-tą pierwszą. Następnie . $p_n$ $p_{n+1}-p_n = O(\log^2 p_n)$

Mamy deterministyczny algorytm wielomianowego czasu dla problemu, po prostu uruchamiając test pierwszeństwa dla każdej liczby większej niż zaczynając od . (Oczywiście powinno być wystarczająco duże; dla małych traktowaliśmy osobno.) $n$ $n+1$ $n$ $n$

Ale nie jestem pewien, czy można to udowodnić bezwarunkowo.

— Hsien-Chih Chang 張顯之
źródło

Jestem ciekawy, jak standardowa jest hipoteza Craméra. Miałem wrażenie, że szanse były przeciwne.

— Cong Han

@Cong: Nie jestem do końca zaznajomiony z przypuszczeniem i mam wrażenie, że mamy dowody na wyniki liczbowe, a także na model losowy. Czy istnieją przesłanki, że przypuszczenie może być fałszywe? Może powinienem powiedzieć „silny” zamiast „standardowy”.

— Hsien-Chih Chang 14 之

@ Hsien-Chih: Wiem bardzo niewiele o tym (poza kilkoma pogłoskami i chwilowym zainteresowaniem projektami Polymath), ale ten artykuł Granville, powiązany z wiki na temat przypuszczenia, wydaje się sugerować: dartmouth.edu/~ szansa / szansa / aktualności / for_chance_news / Riemann /…

— Cong Han

@Cong: Wydaje się, że to miła lektura, przejrzę ją za kilka dni!

— Hsien-Chih Chang 14 之