Kompleksitas fungsi eksponensial

Kita tahu bahwa fungsi eksponensial atas bilangan asli tidak dapat dihitung dalam waktu polinomial, karena ukuran output tidak dibatasi secara polinomi dalam ukuran input.$\exp(x,y) = x^y$

Apakah ini alasan utama untuk kesulitan menghitung fungsi eksponensial, atau apakah eksponensial pada dasarnya sulit untuk dihitung, terlepas dari pertimbangan ini?

Apa kerumitan grafik bit dari fungsi eksponensial?

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

Berikut adalah beberapa batas atas.

Dengan kuadrat ulang, masalahnya ada di PSPACE.

Ada batas atas yang sedikit lebih baik. Masalahnya adalah kasus khusus dari masalah BitSLP: Diberikan program garis lurus mulai dari 0 dan 1 dengan penambahan, pengurangan, dan perkalian yang mewakili bilangan bulat N , dan diberikan i ∈ℕ, tentukan apakah bit ke- i (dihitung dari bit paling signifikan) dari representasi biner N adalah 1. Masalah BitSLP adalah dalam hierarki penghitungan ( CH ) [ABKM09]. (Dinyatakan dalam [ABKM09] bahwa dapat ditunjukkan bahwa masalah BitSLP ada di PH ^{PP PP PP PP} .)

Keanggotaan untuk CH sering dianggap sebagai bukti bahwa masalahnya tidak mungkin sulit PSPACE, karena kesetaraan CH = PSPACE menyiratkan bahwa hierarki penghitungan runtuh. Namun, saya tidak tahu seberapa kuat bukti ini dianggap.

Adapun kekerasannya, BitSLP terbukti # P-hard di kertas yang sama [ABKM09]. Namun, buktinya tampaknya tidak menyiratkan kekerasan bahasa X dalam pertanyaan.

Referensi

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen dan Peter Bro Miltersen. Pada kompleksitas analisis numerik. Jurnal SIAM tentang Komputer , 38 (5): 1987–2006, Januari 2009. http://dx.doi.org/10.1137/070697926

Bukan jawaban yang lengkap, tetapi setidaknya sebagian.

Saya perhatikan bahwa dua jawaban yang telah muncul sejauh ini belum menyebutkan fakta bahwa ada $O(n^{1+\omega})$ algoritma untuk menghitung eksponensial modular mana n adalah jumlah bit dalam z , dan di mana ω adalah eksponen yang sesuai dengan algoritma multiplikasi tercepat. Jadi bit yang kurang signifikan dari eksponensial dapat dihitung secara efisien (dalam O ( n 3 ) atau kurang).$x^y ~\mbox{mod }z$$n$$z$$\omega$$O(n^3)$

Cara melakukannya cukup sederhana: Anda dapat menghitung , c 2 = x 2 mod  z , c j = c 2 j - 1 mod  z . Jelas c j = x 2 j mod  z , dan juga x y ≡ $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$ , tapi karena hanya ada n istilah c j ini hanya memakan waktu$x^y \equiv \prod_j c_j^{y_j}~\mbox{mod }z$$n$$c_j$$n$ perkalian.

Selanjutnya, kita dapat menulis sebagai ( Σ n i = 0 2 i x i ) y , sehingga bit paling signifikan yang bersesuaian kira-kira 2 n y juga dapat efisien menghitung seperti ini hanya akan tergantung pada pada yang paling sedikit signifikan dari x .$x^y$$(\sum_{i=0}^n 2^i x_i)^y$$2^{ny}$$x$

Jadi masalah hanya nyata hal disebabkan oleh bit menuju pusat .$x^y$

[Jawaban ini menjelaskan beberapa aspek menarik tentang jawaban Per Vognsen . Ini bukan jawaban langsung untuk pertanyaan OP, namun dapat membantu dalam menyelesaikan pertanyaan seperti itu.]

Pertama, lihat tautan berikut: $i$$\pi$$i-1$

Selanjutnya, lihat pendapat Dick Lipton tentang hal ini: $i$$\pi$$\rm SC$

$\rm SC$