Una función doble exponencial es una constante elevada a la potencia de una función exponencial . La fórmula general es(donde a > 1 yb > 1), que crece mucho más rápidamente que una función exponencial. Por ejemplo, si a = b = 10:
- f (0) = 10
- f (1) = 10 10
- f (2) = 10 100 = googol
- f (3) = 10 1000
- f (100) = 10 10 100 = googolplex .
Los factoriales crecen más rápidamente que las funciones exponenciales, pero mucho más lentamente que las funciones doblemente exponenciales. Sin embargo, la tetración y la función de Ackermann crecen más rápido. Consulte la notación Big O para una comparación de la tasa de crecimiento de varias funciones.
La inversa de la función exponencial doble es el logaritmo doble ln (ln ( x )).
Secuencias doblemente exponenciales
Se dice que una secuencia de enteros positivos (o números reales) tiene una tasa de crecimiento doblemente exponencial si la función que da el n- ésimo término de la secuencia está acotada por encima y por debajo por funciones doblemente exponenciales de n . Ejemplos incluyen
- Los primos armónicos: Los primos p, en los que la secuencia 1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / p excede 0, 1, 2, 3, ...
- Los primeros números, que comienzan con 0, son 2, 5, 277, 5195977, ... (secuencia A016088 en la OEIS )
- Los elementos de la secuencia de Sylvester (secuencia A000058 en la OEIS )
- El número de funciones booleanas k -ary :
- donde A ≈ 1,306377883863 es la constante de Mills .
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. Muestran que tales secuencias se pueden formar redondeando al número entero más cercano los valores de una función doblemente exponencial con exponente medio 2. [1] Ionaşcu y Stănică describen algunas condiciones más generales suficientes para que una secuencia sea el piso de una secuencia doblemente exponencial. más una constante. [2]
Aplicaciones
Complejidad algorítmica
En la teoría de la complejidad computacional , algunos algoritmos toman un tiempo doblemente exponencial:
- Cada procedimiento de decisión para la aritmética de Presburger requiere probablemente al menos un tiempo doblemente exponencial [3]
- Calcular una base de Gröbner sobre un campo. En el peor de los casos, una base de Gröbner puede tener un número de elementos doblemente exponencial en el número de variables. Por otro lado, la complejidad del peor de los casos de los algoritmos de base de Gröbner es doblemente exponencial en el número de variables, así como en el tamaño de la entrada. [4]
- Encontrar un conjunto completo de unificadores asociativo-conmutativos [5]
- Satisfactorio CTL + (que es, de hecho, 2-EXPTIME -completo) [6]
- La eliminación del cuantificador en campos cerrados reales requiere un tiempo doblemente exponencial (ver Descomposición algebraica cilíndrica ).
- Calcular el complemento de una expresión regular [7]
En algunos otros problemas en el diseño y análisis de algoritmos, se utilizan secuencias doblemente exponenciales dentro del diseño de un algoritmo más que en su análisis. Un ejemplo es el algoritmo de Chan para calcular cascos convexos , que realiza una secuencia de cálculos usando valores de prueba h i = 2 2 i (estimaciones para el tamaño de salida eventual), tomando tiempo O ( n log h i ) para cada valor de prueba en la secuencia. . Debido al doble crecimiento exponencial 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 tanto, el tiempo total del algoritmo es O ( n log h ) donde h es el tamaño de salida real. [8]
Teoría de los números
Algunos límites teóricos de números son doble exponencial. Se sabe que los números perfectos impares con n factores primos distintos son como máximo
resultado de Nielsen (2003). [9] El volumen máximo de un politopo de celosía d con k ≥ 1 puntos de celosía interior es como máximo
un resultado de Pikhurko. [10]
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 número primo de 79 dígitos en EDSAC 1 en 1951. [11]
Biología teórica
En la dinámica de la población, a veces se supone que el crecimiento de la población humana es doble exponencial. Varfolomeyev y Gurevich [12] ajustan experimentalmente
donde N ( y ) es la población en millones en el año y .
Física
En el modelo de oscilador de Toda de autopulsación , el logaritmo de amplitud varía exponencialmente con el tiempo (para grandes amplitudes), por lo que la amplitud varía como función doblemente exponencial del tiempo. [13]
Se ha observado que las macromoléculas dendríticas crecen de forma doblemente exponencial. [14]
Referencias
- ^ Aho, AV ; Sloane, NJA (1973), "Algunas secuencias doblemente exponenciales" , Fibonacci Quarterly , 11 : 429–437.
- ^ Ionascu, 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.
- ^ Fischer, MJ y Michael O. Rabin , 1974, " " Complejidad súper exponencial de la aritmética de Presburger. Archivado el 15 de septiembre de 2006en la Wayback Machine " Actas del Simposio SIAM-AMS en Matemáticas Aplicadas Vol. 7 : 27–41
- ^ Dubé, Thomas W. La estructura de ideales polinomiales y bases de Gröbner. SIAM Journal on Computing , 1990, vol. 19, no 4, pág. 750-773.
- ^ Kapur, Deepak; Narendran, Paliath (1992), "Complejidad doble exponencial de calcular un conjunto completo de unificadores de CA", Proc. Séptimo IEEE Symp. Lógica en Ciencias de la Computación (LICS 1992) , págs. 11-21, doi : 10.1109 / LICS.1992.185515 , ISBN 0-8186-2735-2, S2CID 206437926.
- ^ Johannsen, Jan; Lange, Martin (2003), "CTL + está completo para el doble de tiempo exponencial", en Baeten, Jos CM; Lenstra, Jan Karel ; Parrow, Joachim; Woeginger, Gerhard J. (eds.), Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (PDF) , Lecture Notes in Computer Science, 2719 , Springer-Verlag, págs. 767–775, doi : 10.1007 / 3-540-45061-0_60 , ISBN 978-3-540-40493-4, archivado desde el original (PDF) el 30 de septiembre de 2007 , consultado el 22 de diciembre de 2006.
- ^ Gruber, Hermann; Holzer, Markus (2008). "Autómatas finitos, conectividad Digraph y tamaño de expresión regular" (PDF) . Actas del 35º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 2008) . 5126 . págs. 39–50. doi : 10.1007 / 978-3-540-70583-3_4 .
- ^ Chan, TM (1996), "Algoritmos óptimos de cascos convexos sensibles a la salida en dos y tres dimensiones", Geometría discreta y computacional , 16 (4): 361–368, doi : 10.1007 / BF02712873 , MR 1414961
- ^ Nielsen, Pace P. (2003), "Un límite superior para números perfectos impares" , INTEGERS: The Electronic Journal of Combinatorial Number Theory , 3 : A14.
- ^ Pikhurko, Oleg (2001), "Puntos de celosía en politopos de celosía", Mathematika , 48 (1–2): 15–24, arXiv : math / 0008028 , Bibcode : 2000math ...... 8028P , doi : 10.1112 / s0025579300014339
- ^ Miller, JCP; Wheeler, DJ (1951), "Números primos grandes", Nature , 168 (4280): 838, Bibcode : 1951Natur.168..838M , doi : 10.1038 / 168838b0.
- ^ 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, doi : 10.1006 / jtbi.2001.2384 , PMID 11829357.
- ^ Kouznetsov, D .; Bisson, J.-F .; Li, J .; Ueda, K. (2007), "Láser autopulsante como oscilador Toda: Aproximación a través de funciones elementales" , Journal of Physics A , 40 (9): 1–18, Bibcode : 2007JPhA ... 40.2107K , doi : 10.1088 / 1751-8113 / 40/9/016.
- ^ Kawaguchi, Tohru; Walker, Kathleen L .; Wilkins, Charles L .; Moore, Jeffrey S. (1995). "Doble crecimiento de dendrímero exponencial". Revista de la Sociedad Química Estadounidense . 117 (8): 2159–2165. doi : 10.1021 / ja00113a005 .