Czy ustalenie, czy istnieje liczba pierwsza w przedziale, o którym wiadomo, że jest w P czy NP-zupełna?

Widziałem z tego postu przy przepełnieniu stosu, że istnieją pewne stosunkowo szybkie algorytmy przesiewania przedziału liczb, aby sprawdzić, czy jest liczba pierwsza w tym przedziale. Czy to jednak oznacza, że ogólny problem decyzyjny: (Czy istnieje liczba pierwsza w przedziale?) Znajduje się w P. (Było wiele odpowiedzi na ten post, których nie przeczytałem, więc przepraszam, jeśli to pytanie jest duplikat lub niepotrzebne).

Z jednej strony, jeśli przedział jest wystarczająco duży (na przykład ), wówczas stosuje się coś takiego jak Postulat Bertranda i w tym przedziale zdecydowanie jest liczba pierwsza. Wiem jednak również, że między dwoma liczbami pierwszymi występują arbitralnie duże luki (na przykład . $[N,2N]$ $[N!,N!+ N]$

Nawet jeśli problem decyzyjny dotyczy PI, nie widzimy, jak odpowiedni problem wyszukiwania jest również możliwy do rozwiązania, ponieważ, wówczas możemy nie być w stanie korzystać z tych samych właściwości dotyczących znanego rozkładu liczb pierwszych podczas wyszukiwania binarnego.

complexity-theory np polynomial-time primes Ari
źródło

Odpowiedzi:

Twój problem jest następujący:

Dane wejściowe: liczby całkowite Pytanie: czy istnieje liczba pierwsza w ? $\ell,u$
$[\ell,u]$

O ile mi wiadomo, nie wiadomo, czy problem występuje w P, czy nie.

Oto co wiem:

Testy pierwotności (biorąc pod uwagę pojedynczą liczbę, sprawdź, czy jest liczbą pierwszą) są w P, więc jeśli zakres jest wystarczająco mały, możesz wyczerpująco przetestować każdą liczbę w zakresie, aby sprawdzić, czy jest liczbą pierwszą - ale to nie prowadzi do algorytm ogólny.
$n$ $O((\log n)^2)$ $\ell,\ell+1,\ell+2,\ell+3,\dots$ $u$ $O((\log \ell)^2)$

Niestety, znane wyniki dla pierwszych luk nie wydają się wystarczająco silne, aby bezwarunkowo udowodnić, że problem dotyczy P.
$r$ $[\ell,u]$ $[\ell,u]$ $u$ $1/\log n$ $O(\log u)$ $[\ell,u]$ $O((u-l) \log(u-l))$
Prawdopodobnie można zastosować metody przesiewania, aby poprawić czas pracy w praktyce (np. Aby uniknąć wykonywania testów pierwotności na liczbach, które można podzielić przez małą liczbę pierwszą). Nie wiem, czy można wykazać, że prowadzi to do jakiejkolwiek asymptotycznej poprawy.
Z powodu tych technik problem jest prawdopodobnie łatwy w praktyce.
Z uwagi na powyższe uwagi osobiście wątpię, aby problem był NP-zupełny.

DW
źródło

O (ℓ u)

$O(\ell u)$

O (poly (\log u))

$O(\text{poly}(\log u))$

O (poly (\log u))

$O(\text{poly}(\log u))$

O (poly (u))

$O(\text{poly}(u))$

\log u

$\log u$

u

$u$

Nie ma potrzeby, wyjaśniłeś moje zamieszanie. Wielkie dzięki!

Quelklef