stringtranslate.com

Función exponencial doble

Una función exponencial doble (curva roja) comparada con una función exponencial simple (curva azul).

Una función exponencial doble es una constante elevada a la potencia de una función exponencial . La fórmula general es (donde a > 1 y b > 1), que crece mucho más rápido que una función exponencial. Por ejemplo, si a = b = 10:

Los factoriales crecen más rápido que las funciones exponenciales, pero mucho más lentamente que las funciones exponenciales dobles. Sin embargo, la tetración y la función de Ackermann crecen más rápido. Consulte la notación Big O para ver una comparación de la tasa de crecimiento de varias funciones.

La inversa de la función exponencial doble es el logaritmo doble log(log( x )). La función exponencial doble compleja es entera , debido a que es la composición de dos funciones enteras y .

Sucesiones exponenciales dobles

Se dice que una secuencia de números enteros positivos (o números reales) tiene una tasa de crecimiento exponencial doble si la función que da el término n de la secuencia está acotada superior e inferiormente por funciones exponenciales dobles de n . Algunos ejemplos incluyen

Aho y Sloane observaron que en varias secuencias de números enteros importantes , cada término es una constante más el cuadrado del término anterior. Demuestran que dichas secuencias se pueden formar redondeando al entero más cercano los valores de una función exponencial doble con exponente medio 2. [1] Ionaşcu y Stănică describen algunas condiciones suficientes más generales para que una secuencia sea el piso de una secuencia exponencial doble más una constante. [2]

Aplicaciones

Complejidad algorítmica

En la teoría de la complejidad computacional , 2-EXPTIME es la clase de problemas de decisión que se pueden resolver en tiempo exponencial doble. Es equivalente a AEXPSPACE, el conjunto de problemas de decisión que se pueden resolver mediante una máquina de Turing alternada en el espacio exponencial, y es un superconjunto de EXPSPACE . [3] Un ejemplo de un problema en 2-EXPTIME que no está en EXPTIME es el problema de probar o refutar afirmaciones en la aritmética de Presburger . [4]

En algunos otros problemas en el diseño y análisis de algoritmos, las secuencias exponenciales dobles se utilizan dentro del diseño de un algoritmo en lugar de en su análisis. Un ejemplo es el algoritmo de Chan para calcular envolventes convexas , que realiza una secuencia de cálculos utilizando valores de prueba h i  = 2 2 i (estimaciones para el tamaño de salida final), tomando tiempo O( n  log  h i ) para cada valor de prueba en la secuencia. Debido al crecimiento exponencial doble de estos valores de prueba, el tiempo para cada cálculo en la secuencia crece exponencialmente como una función de i , y el tiempo total está dominado por el tiempo para el paso final de la secuencia. Por lo tanto, el tiempo total para el algoritmo es O( n  log  h ) donde h es el tamaño de salida real. [5]

Teoría de números

Algunos límites teóricos de números son doblemente exponenciales. Se sabe que los números perfectos impares con n factores primos distintos tienen como máximo , un resultado de Nielsen (2003). [6]

El volumen máximo de un politopo en una red entera de dimensión d con k ≥ 1 puntos de red interior es como máximo

un resultado de Pikhurko (2001). [7]

El número primo más grande conocido en la era electrónica ha crecido aproximadamente como una función exponencial doble del año desde que Miller y Wheeler encontraron un primo de 79 dígitos en EDSAC 1 en 1951. [8]

Biología teórica

En dinámica de poblaciones, a veces se supone que el crecimiento de la población humana es doblemente exponencial. Varfolomeyev y Gurevich [9] ajustaron experimentalmente

donde N ( y ) es la población en millones en el año y .

Física

En el modelo de autopulsación del oscilador de Toda , el logaritmo de la amplitud varía exponencialmente con el tiempo (para amplitudes grandes), por lo que la amplitud varía como una función exponencial doble del tiempo. [10]

Se ha observado que las macromoléculas dendríticas crecen de forma doblemente exponencial. [11]

Referencias

  1. ^ Aho, AV ; Sloane, NJA (1973), "Algunas secuencias doblemente exponenciales", Fibonacci Quarterly , 11 : 429–437.
  2. ^ Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), "Asintóticas efectivas para algunas recurrencias no lineales y secuencias casi doblemente exponenciales" (PDF) , Acta Mathematica Universitatis Comenianae , LXXIII (1): 75–87.
  3. ^ Christos Papadimitriou , Computational Complexity (1994), ISBN 978-0-201-53082-7 . Sección 20.1, corolario 3, página 495. 
  4. ^ Fischer, MJ y Michael O. Rabin , 1974, "Complejidad superexponencial de la aritmética de Presburger". Archivado el 15 de septiembre de 2006 en Wayback Machine . Actas del Simposio SIAM-AMS sobre Matemáticas Aplicadas, vol. 7 : 27–41.
  5. ^ Chan, TM (1996), "Algoritmos de casco convexo sensibles a la salida óptima en dos y tres dimensiones", Geometría discreta y computacional , 16 (4): 361–368, doi : 10.1007/BF02712873 , MR  1414961
  6. ^ Nielsen, Pace P. (2003), "Un límite superior para números perfectos impares", INTEGERS: The Electronic Journal of Combinatorial Number Theory , 3 : A14.
  7. ^ Pikhurko, Oleg (2001), "Puntos reticulares en politopos reticulares", Mathematika , 48 (1–2): 15–24, arXiv : math/0008028 , Bibcode :2000math......8028P, doi :10.1112/s0025579300014339
  8. ^ Miller, JCP; Wheeler, DJ (1951), "Números primos grandes", Nature , 168 (4280): 838, Bibcode :1951Natur.168..838M, doi : 10.1038/168838b0.
  9. ^ Varfolomeyev, SD; Gurevich, KG (2001), "El crecimiento hiperexponencial de la población humana en una escala macrohistórica", Journal of Theoretical Biology , 212 (3): 367–372, Bibcode :2001JThBi.212..367V, doi :10.1006/jtbi.2001.2384, PMID  11829357.
  10. ^ Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Láser autopulsado como oscilador Toda: aproximación a través de funciones elementales", Journal of Physics A , 40 (9): 1–18, Bibcode :2007JPhA...40.2107K, CiteSeerX 10.1.1.535.5379 , doi :10.1088/1751-8113/40/9/016, S2CID  53330023 .
  11. ^ Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Crecimiento exponencial doble del dendrímero". Revista de la Sociedad Química Americana . 117 (8): 2159–2165. doi :10.1021/ja00113a005.