Complejidad de la función exponencial

36

Sabemos que la función exponencial sobre números naturales no es computable en tiempo polinómico, porque el tamaño de la salida no está polinomialmente limitado en el tamaño de las entradas.exp(x,y)=xy

¿Es esta la razón principal de la dificultad de calcular la función exponencial, o la exponenciación es inherentemente difícil de calcular, independientemente de esta consideración?

¿Cuál es la complejidad del gráfico de bits de la función exponencial?

{x,y,ix,y,iN and the i-th bit of xy is 1}
Peter
fuente
Cambié la noción "EXP" a "L", ya que EXP es el nombre de una clase de complejidad famosa y puede generar confusión.
MS Dousti
Si está restringido a una potencia de 2, entonces es . Además, la gráfica de la exponenciación tiene baja complejidad. L A C 0 Γ e x p = { ( x , y , z ) : x y = z }xLAC0Γexp={(x,y,z):xy=z}
Kaveh
3
Sadeq: Si quieres evitar las clases de complejidad, L no es mejor que EXP ... Cambié a X.
Peter
@ Peter: En el contexto, L es seguramente un "lenguaje" en lugar de la clase de complejidad Log-space. De todos modos, X es una opción mucho mejor.
MS Dousti
@Kaveh: La pregunta establece que se trata de la función exponencial en los números naturales.
Tsuyoshi Ito

Respuestas:

17

Aquí hay algunos límites superiores.

Al cuadrar repetidamente, el problema está en PSPACE.

Hay un límite superior ligeramente mejor. El problema es un caso especial del problema BitSLP: dado un programa de línea recta que comienza en 0 y 1 con suma, resta y multiplicación que representa un número entero N , y dado i ∈ℕ, decida si el bit i (contando desde el el bit menos significativo) de la representación binaria de N es 1. El problema de BitSLP está en la jerarquía de conteo ( CH ) [ABKM09]. (Se indica en [ABKM09] que se puede demostrar que el problema de BitSLP está en PH PP PP PP PP ).

La pertenencia a CH a menudo se considera como una evidencia de que es poco probable que el problema sea difícil para PSPACE, porque la igualdad CH = PSPACE implica que la jerarquía de conteo colapsa. Sin embargo, no sé qué tan fuerte se considera esta evidencia.

En cuanto a la dureza, se muestra que BitSLP es # P-duro en el mismo papel [ABKM09]. Sin embargo, la prueba allí no parece implicar ninguna dureza del lenguaje X en la pregunta.

Referencias

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen y Peter Bro Miltersen. Sobre la complejidad del análisis numérico. SIAM Journal on Computing , 38 (5): 1987–2006, enero de 2009. http://dx.doi.org/10.1137/070697926

Tsuyoshi Ito
fuente
12

No es una respuesta completa, pero al menos parcial.

Noté que las dos respuestas que han aparecido hasta ahora no han mencionado el hecho de que hay un algoritmo para calcular el exponencial modular x y mod  z donde n es el número de bits en z , y donde ω es el exponente correspondiente al algoritmo de multiplicación más rápido. Por lo tanto, los bits menos significativos del exponencial se pueden calcular de manera eficiente (en O ( n 3 ) o menos).O(n1+ω)xy mod znzωO(n3)

La forma de hacerlo es bastante simple: puede calcular , c 2 = x 2 mod  z , c j = c 2 j - 1 mod  z . Claramente c j = x 2 j mod  z , y entonces x yj c y j j mod  z , pero como solo hay n términos c j esto solo toma nc1=xc2=x2 mod zcj=cj12 mod zcj=x2j mod zxyjcjyj mod zncjn multiplicaciones

xy(i=0n2ixi)y2nyx

xy

Joe Fitzsimons
fuente
1
Hay una relación interesante entre esta respuesta y la mía. Si no me equivoco, una descripción general del algoritmo en [ABKM09 ] citado en mi respuesta es combinar esta idea con el teorema del resto chino para obtener bits más altos.
Tsuyoshi Ito
Ah, no me había dado cuenta de eso.
Joe Fitzsimons
6

[Esta respuesta explica algunos aspectos interesantes sobre la respuesta de Per Vognsen . No es una respuesta directa a la pregunta del OP, pero puede ayudar a resolver tales preguntas.]

iπi1

iπSC

SC

MS Dousti
fuente