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?
${⟨ x, y, i ⟩ ∣ x, y, i \in N and the i -th bit of x^{y} is 1}$ $\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$

cc.complexity-theory nt.number-theory

— Piotr
źródło

Zmieniłem pojęcie „EXP” na „L”, ponieważ EXP to nazwa znanej klasy złożoności i może prowadzić do zamieszania.

— MS Dousti

Jeśli jest ograniczone do potęgi 2, to oznacza . Również wykres potęgowania ma niską złożoność.

x

$x$

L

$L$

A C^{0}

$AC^0$

Γ e x p = {(x, y, z) : x^{y} = z}

$\Gamma exp=\{(x,y,z) : x^y=z\}$

— Kaveh

Sadeq: Jeśli chcesz uniknąć klas złożoności, L nie jest w żaden sposób lepszy niż EXP ... Zmieniłem to na X.

— Peter

@Peter: W kontekście L jest z pewnością „językiem”, a nie klasą złożoności przestrzeni logów. W każdym razie X jest znacznie lepszym wyborem.

— MS Dousti

@Kaveh: Pytanie mówi, że chodzi o funkcję wykładniczą na liczbach naturalnych.

— Tsuyoshi Ito

Odpowiedzi:

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

— Tsuyoshi Ito
źródło

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). $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_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 . $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$

— Joe Fitzsimons
źródło

Istnieje interesujący związek między tą odpowiedzią a moją. Jeśli się nie mylę, zgrubny przegląd algorytmu w [ABKM09 ] cytowany w mojej odpowiedzi polega na połączeniu tego pomysłu z twierdzeniem o chińskiej reszcie w celu uzyskania wyższych bitów.

— Tsuyoshi Ito

Ach, nie zdawałem sobie z tego sprawy.

— Joe Fitzsimons

[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$ $\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”. $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$

— MS Dousti
źródło