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.
¿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?
Respuestas:
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
fuente
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 z n z ω 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 y ≡ ∏ j c y j j mod z , pero como solo hay n términos c j esto solo toma nc1=x c2=x2 mod z cj=c2j−1 mod z cj=x2j mod z xy≡∏jcyjj mod z n cj n multiplicaciones
fuente
[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.]
fuente