Menemukan prime lebih besar dari batasan yang diberikan

Apakah algoritme waktu polinomial deterministik yang dikenal untuk masalah berikut:

Input: angka alami $n$ (dalam pengkodean biner)

Output: bilangan prima $p > n$ .

(Menurut daftar masalah terbuka oleh Leonard Adleman, masalahnya terbuka pada 1995.)

Hasil tanpa syarat terbaik saat ini diberikan oleh Odlyzko, yang menemukan di $p >N$ waktu. Dugaan kuat dalam proyek Polymath4 berusaha untuk menyelesaikan jika ini dapat dilakukan dalam waktu polinomial, di bawah asumsi teoretik-bilangan yang masuk akal seperti GRH.$O(N^{1/2 + o(1)})$

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

Saat ini proyek berupaya menjawab pertanyaan berikut:

Diberi angka dan interval antara N dan 2 N , waktu check in O ( N $N$$N$$2N$untuk beberapac>0jika interval mengandung prima.$O(N^{1/2 - c})$$c>0$

Sejauh ini, mereka memiliki strategi yang menentukan paritas jumlah bilangan prima dalam interval.

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

Dengan asumsi dugaan standar dalam teori bilangan, yang menyatakan itu

Dugaan Cramér : Biarkan menjadi perdana ke-n. Kemudian p n + 1 - p n = O ( log 2 p n ) .$p_n$$p_{n+1}-p_n = O(\log^2 p_n)$

Kami memiliki algoritma polinomial-waktu deterministik untuk masalah, hanya dengan menjalankan tes primality pada setiap nomor lebih besar dari mulai dari n + 1 . (Tentu saja, n harus cukup besar; untuk n kecil kami diperlakukan secara terpisah.)$n$$n+1$$n$$n$

Tapi saya tidak yakin ini bisa dibuktikan tanpa syarat.