Complexidade da função exponencial

Sabemos que a função exponencial sobre números naturais não é computável em tempo polinomial, porque o tamanho da saída não é polinomialmente limitado no tamanho das entradas.$\exp(x,y) = x^y$

Essa é a principal razão da dificuldade de calcular a função exponencial ou a exponenciação é inerentemente difícil de calcular, independentemente dessa consideração?

Qual é a complexidade do gráfico de bits da função exponencial?

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

Aqui estão alguns limites superiores.

Ao quadrado repetido, o problema está no PSPACE.

Existe um limite superior ligeiramente melhor. O problema é um caso especial do problema do BitSLP: dado um programa linear a partir de 0 e 1 com adição, subtração e multiplicação representando um número inteiro N , e dado i ∈ℕ, decida se o i- ésimo bit (contando do bit menos significativo) da representação binária de N é 1. O problema do BitSLP está na hierarquia de contagem ( CH ) [ABKM09]. (É declarado em [ABKM09] que pode ser demonstrado que o problema do BitSLP está em PH ^{PP PP PP PP} .)

A associação ao CH é frequentemente considerada uma evidência de que é improvável que o problema seja difícil para o PSPACE, porque a igualdade CH = PSPACE implica que a hierarquia de contagem entra em colapso. No entanto, não sei quão forte essa evidência é considerada.

Quanto à dureza, o BitSLP é mostrado com # P-hard no mesmo documento [ABKM09]. No entanto, a prova não parece implicar nenhuma dureza da linguagem X na questão.

Referências

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen e Peter Bro Miltersen. Sobre a complexidade da análise numérica. SIAM Journal on Computing , 38 (5): 1987–2006, janeiro de 2009. http://dx.doi.org/10.1137/070697926

Não é uma resposta completa, mas pelo menos parcial.

Percebo que as duas respostas que apareceram até agora não mencionaram o fato de que existe um algoritmo para calcular o exponencial modular x y mod  z onde n é o número de bits em z e onde ω é o expoente correspondente ao algoritmo de multiplicação mais rápido. Portanto, os bits menos significativos da exponencial podem ser calculados com eficiência (em O ( n 3 ) ou menos).$O(n^{1+\omega})$$x^y ~\mbox{mod }z$$n$$z$$\omega$$O(n^3)$

A maneira de fazer isso é bastante simples: você pode calcular , c 2 = x 2 mod  z , c j = c 2 j - 1 mod  z . Claramente c j = x 2 j mod  z , e então x y ∏ ≡ j c y j j mod  z , mas como existem apenas n termos c j, isso leva apenas $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$ multiplicações.

Além disso, podemos escrever como ( ∑ n i = 0 2 i x i ) y , para que os bits mais significativos que correspondam a aproximadamente 2 n y também possam ser calculados com eficiência, pois dependerão apenas do bit mais significativo de x .$x^y$$(\sum_{i=0}^n 2^i x_i)^y$$2^{ny}$$x$

Portanto, os únicos termos reais do problema são causados ​​por bits no centro de .$x^y$

[Esta resposta explica alguns aspectos interessantes sobre a resposta de Per Vognsen . Não é uma resposta direta à pergunta do OP, mas pode ajudar na resolução de tais questões.]

Primeiro, dê uma olhada no seguinte link: Fórmula de Bailey-Borwein-Plouffe (ou simplesmente fórmula BBP). É uma maneira de calcular o ésimo número irracional π , sem calcular primeiro os primeiros i - 1 bits. O artigo destaca que também existem fórmulas do tipo BPP para outros números irracionais.$i$$\pi$$i-1$

$i$$\pi$$\rm SC$

$\rm SC$