Complexidade da função exponencial

36

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)=xy

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?

{x,y,ix,y,iN and the i-th bit of xy is 1}
Pedro
fonte
Alterei a noção "EXP" para "L", pois EXP é o nome de uma famosa classe de complexidade e pode causar confusão.
MS Dousti
Se estiver restrito a uma potência de 2, então é . Além disso, o gráfico da exponenciação possui baixa complexidade. G A C 0 Γ de e x p = { ( x , y , z ) : x y = z }xLAC0Γexp={(x,y,z):xy=z}
Kaveh
3
Sadeq: Se você quer evitar classes de complexidade, L não é de forma melhor do que EXP ... mudou para X.
Peter
@ Peter: No contexto, L é certamente uma "linguagem" em vez da classe de complexidade do espaço de log. Enfim, X é uma escolha muito melhor.
MS Dousti 30/09/10
@ Kaveh: A pergunta afirma que se trata da função exponencial nos números naturais.
Tsuyoshi Ito

Respostas:

17

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

Tsuyoshi Ito
fonte
12

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(n1+ω)xy mod znzωO(n3)

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 nc1=xc2=x2 mod zcj=cj12 mod zcj=x2j mod zxyjcjyj mod zncjn 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 .xy(i=0n2ixi)y2nyx

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

Joe Fitzsimons
fonte
1
Existe uma relação interessante entre essa resposta e a minha. Se não me engano, uma visão geral aproximada do algoritmo em [ABKM09 ] citada em minha resposta é combinar essa ideia com o teorema do restante chinês para obter bits mais altos.
Tsuyoshi Ito
Ah, eu não tinha percebido isso.
Joe Fitzsimons
6

[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πi1

iπSC

SC

MS Dousti
fonte