Złożoność funkcji wykładniczej

Wiemy, że funkcja wykładnicza nad liczbami naturalnymi nie jest obliczalna w czasie wielomianowym, ponieważ wielkość wyjścia nie jest wielomianowo ograniczona wielkością danych wejściowych.$\exp(x,y) = x^y$

Czy jest to główny powód trudności w obliczeniu funkcji wykładniczej, czy też wykładnictwo wykładnicze jest z natury trudne do obliczenia, niezależnie od tego?

Jaka jest złożoność grafu bitowego funkcji wykładniczej?

$$\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$$

Oto niektóre górne granice.

Przez powtarzanie kwadratu problem występuje w PSPACE.

Jest nieco lepsza górna granica. Problem jest szczególnym przypadkiem problemu BitSLP: Biorąc pod uwagę program prosty rozpoczynający się od 0 i 1 z dodawaniem, odejmowaniem i mnożeniem reprezentującym liczbę całkowitą N , i biorąc pod uwagę i ∈ℕ, decyduje, czy i -ty bit (licząc od najmniej znaczący bit) binarnej reprezentacji N wynosi 1. Problem BitSLP jest w hierarchii zliczania ( CH ) [ABKM09]. (W [ABKM09] stwierdzono, że można wykazać, że problem BitSLP występuje w PH ^{PP PP PP PP} .)

Przynależność do CH jest często uważana za dowód, że problem prawdopodobnie nie będzie trudny w PSPACE, ponieważ równość CH = PSPACE oznacza załamanie hierarchii liczenia. Nie wiem jednak, jak silny jest ten dowód.

Jeśli chodzi o twardość, BitSLP jest pokazany jako # P-twardy na tym samym papierze [ABKM09]. Jednak dowód na to, że nie wydaje się sugerować twardości języka X w pytaniu.

Referencje

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen i Peter Bro Miltersen. O złożoności analizy numerycznej. SIAM Journal on Computing , 38 (5): 1987–2006, styczeń 2009. http://dx.doi.org/10.1137/070697926

Nie jest to pełna odpowiedź, ale przynajmniej częściowa.

Zauważam, że dwie odpowiedzi, które pojawiły się do tej pory, nie wspominają o fakcie, że istnieje algorytm do obliczania modułowej wykładniczej gdzie jest liczba bitów w , a gdzie jest wykładnikiem odpowiadającym algorytmowi najszybszego mnożenia. Tak więc mniej znaczące bity wykładnicze można obliczyć wydajnie (w lub mniej).x y mod  z n z ω O ( n 3$O(n^{1+\omega})$$x^y ~\mbox{mod }z$$n$$z$$\omega$$O(n^3)$

Sposób na zrobienie tego jest dość prosty: możesz obliczyć , , . Oczywiście , a więc , ale ponieważ jest tylko terminów to zajmuje tylko mnożenia.c 2 = x 2 mod  z c j = c 2 j - 1 mod  z c j = x 2 j mod  z x y ≡ ∏ j c y j j mod  z n c j$c_1 = x$$c_2 = x^2 ~\mbox{mod }z$$c_j = c_{j-1}^2 ~\mbox{mod }z$$c_j = x^{2^j}~\mbox{mod }z$$x^y \equiv \prod_j c_j^{y_j}~\mbox{mod }z$$n$$c_j$$n$

Ponadto możemy zapisać jako , więc najbardziej znaczące bity, które odpowiadają w przybliżeniu można również skutecznie obliczyć, ponieważ będą one tylko zależą od najbardziej znaczącego bitu . ( ∑ n i = 0 2 i x i ) y 2 n y$x^y$$(\sum_{i=0}^n 2^i x_i)^y$$2^{ny}$$x$

Tak więc jedyne prawdziwe problemy są spowodowane przez bity w kierunku środka .$x^y$

[Ta odpowiedź wyjaśnia kilka interesujących aspektów odpowiedzi Per Vognsena . Nie jest to bezpośrednia odpowiedź na pytanie PO, ale może pomóc w rozwiązaniu takich pytań.]

Najpierw spójrz na następujący link: wzór Bailey-Borwein-Plouffe (lub po prostu wzór BBP). Jest to sposób na obliczenie tego bitu liczby niewymiernej bez uprzedniego obliczenia pierwszych bitów . W artykule wskazano, że istnieją również formuły typu BPP dla innych liczb niewymiernych.π i - $i$$\pi$$i-1$

Następnie spójrz na spojrzenie Dicka Liptona na ten temat: Klasa Cooka zawiera Pi . Artykuł zasadniczo opisuje, że decydowanie o tym fragmencie należy do klasy Steve'a Cooka ( , klasa języków akceptowanych w czasie wielomianowym i przestrzeni poligarytmicznej) oraz że fakt ten jest niezwykle dziwny, jak sam to nazywa wbrew „konwencjonalnej mądrości”.π S $i$$\pi$$\rm SC$

PS: Pod koniec swojego artykułu Dick przyznaje, że algorytm może być poza , ale taka możliwość wykracza poza „praktyczne zastosowanie”.$\rm SC$