Teoretyczna złożoność trudna do sprawdzenia wartości

Funkcja zliczania liczb pierwszych , zdegradowana , jest zdefiniowana jako liczba liczb pierwszych mniejsza lub równa x .$\pi(x)$$x$

Możemy zdefiniować problem decyzyjny z w następujący sposób:$\pi(x)$

Biorąc pod uwagę dwie liczby i n , zapisane binarnie, zdecyduj, czy π ( x ) = n .$x$$n$$\pi(x) = n$

Rozmawiałem dziś z przyjacielem o tym problemie dzisiaj. Dla tego problemu istnieje algorytm czasu pseudopolinialnego - po prostu policz do , używając podziału próby na każdym kroku, aby zobaczyć, ile liczb jest liczbą pierwszą, i sprawdź, czy jest to n . Problem dotyczy także PSPACE, ponieważ właśnie opisany algorytm można zaimplementować tak, aby używał tylko wielomianowej przestrzeni pomocniczej.$x$$n$

Mam jednak problem ze znalezieniem sposobu na umieszczenie tego problemu w niższej klasie złożoności. Nie widzę, jak zbudować weryfikator czasu wielomianowego dla problemu, więc nie jestem pewien, czy jest on w NP, i nie mogę w ogóle wymyślić sposobu na włączenie go do hierarchii wielomianowej.

Jaka jest najbardziej odpowiednia klasa złożoności dla tego problemu?

Dzięki!

To bardzo otwarty problem. Naszkicuję kilka klas, w których problem mógłby „naturalnie” pasować.

$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$\{(x,n)|\pi(x)\leq n\}$$K$$\{(x,n)|\pi(x)\geq n\}$$coK$$K$$coK$

$\pi(X)$$\#P$$\#P\subseteq FPSPACE$$q \leq x$$q$

$\#P$$PP$$\{(x,n)|\pi(x)\leq n\}$$\{(x,n)|\pi(x)\geq n\}$$PP$ (wykonując trochę kręcenia we wspomnianej bazie TM, aby zrównoważyć liczbę ścieżek akceptujących).

$_=$ $\hspace{-0.06 in}\text{,}$

$\;\;\;$$\big[$m$\: 0\leq m < 2^{\lceil \hspace{.02 in}\log_{\hspace{.02 in}2}\hspace{-0.02 in}(x+1)\rceil}\big]$b
$\;\;\;$jeśli x < mnastępnie odrzuć
$\;\;\;$jeśli b=1wtedy:
$\;\;\;\;\;$jeśli m < nnastępnie zaakceptuj inaczej, odrzuć
$\;\;\;$ jeszcze:
$\;\;\;\;\;$jeśli m jest liczbą pierwszą, to zaakceptuj inaczej

.


W szczególności twój problem dotyczy również PP, ponieważ PP jest zamknięty w ramach redukcji tabel prawdy .

W praktyce możesz uzyskać odpowiedź szybciej lub wolniej :-(

Istnieją dość dobre przybliżenia dla π (x). Obliczasz takie przybliżenie, a jeśli jest zbyt daleko, wiesz, że π (x) ≠ n. Na przykład, jeśli n ≥ x, to wiem, że π (x) ≠ n bez obliczania czegokolwiek.

Istnieje szybki algorytm, który określa, czy π (x) jest parzysty czy nieparzysty, działający w O (x ^ (1/2)). Możesz uruchomić ten algorytm, który może wykryć, że parzystość n jest niepoprawna i gotowe. Ma pięćdziesiąt szans, jeśli n jest losową liczbą całkowitą bliską π (x).

Poza tym nie znam żadnej metody, która byłaby szybsza niż obliczanie π (x). Co jest bardzo niewygodne - jeśli napiszę program, który ma wyliczyć π (10 ^ 25), i otrzymam wynik, który oczywiście nie jest zły, nie ma sposobu, aby sprawdzić, czy mój wynik jest poprawny, poza powtórzeniem obliczenie. I nie możesz po prostu powtórzyć obliczeń za pomocą mojego programu, musisz napisać inny program, inaczej nie wykryłbyś, czy mój program ma jakieś błędy, które powodują, że oblicza on nieco inną funkcję niż π (x).

π (x) można łatwo obliczyć w przybliżeniu w przybliżeniu O (n ^ (2/3)), i szybciej z kilkoma naprawdę głębokimi matematykami.