二重指数関数

二重指数関数は、指数関数の累乗された定数です。 一般的な式は( a >1 かつb >1) であり、指数関数よりもはるかに速く増加します。 たとえば、 a = b = 10の場合: ${\displaystyle f(x)=a^{b^{x}}=a^{(b^{x})}}$

• 10 ^{10 x の}関数
• （０）＝１０
• （ １）＝１０^１０
• f (2) = 10 ¹⁰⁰ =グーゴル
• （３）＝１０^{・１０００}
• f (100) = 10 ^{10 100} =グーゴルプレックス。

階乗は指数関数よりも速く増加しますが、二重指数関数よりもはるかに遅くなります。ただし、テトレーションとアッカーマン関数はより速く増加します。さまざまな関数の増加率の比較については、 Big O 表記法を参照してください。

二重指数関数の逆関数は二重対数log(log( x ))です。

正の整数（または実数）の列は、その列のn番目の項を与える関数がnの二重指数関数によって上下に制限される場合、二重指数関数的増加率を持つと言われます。例としては、

• フェルマー数 $${\displaystyle F(m)=2^{2^{m}}+1}$$
• 調和素数:数列1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ pが0、1、2、3、… を超える素数p 。
  最初のいくつかの数字は、0から始まり、2、5、277、5195977、...（OEISのシーケンスA016088）です。
• 二重メルセンヌ数 $${\displaystyle MM(p)=2^{2^{p}-1}-1}$$
• E ≈ 1.264084735305302であるシルベスター数列( OEISの配列A000058 )の要素は、ヴァルディ定数 ( OEISの配列A076393 ) です。$${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor }$$
• k項 ブール関数の数:$${\displaystyle 2^{2^{k}}}$$
• 素数2、11、1361、...（OEISのシーケンスA051254）で、A ≈ 1.306377883863はミルズ定数です。$${\displaystyle a(n)=\left\lfloor A^{3^{n}}\right\rfloor }$$

AhoとSloaneは、いくつかの重要な整数列において、各項が定数と前の項の2乗を足したものになっていることを観察した。彼らは、そのような列は、中間指数が2である二重指数関数の値を最も近い整数に丸めることによって形成できることを示した。^[1] IonaşcuとStănicăは、列が二重指数列の底値と定数を足したものになるための、より一般的な十分条件をいくつか説明している。^[2]

計算複雑性理論において、2-EXPTIMEは二重指数時間で解ける決定問題のクラスである。これは、指数空間で交代チューリングマシンによって解ける決定問題の集合であるAEXPSPACEと同等であり、 EXPSPACEのスーパーセットである。^[3] EXPTIMEにない2-EXPTIMEの問題の例として、プレスブルガー算術における命題の証明または反証の問題が挙げられる。^[4]

アルゴリズムの設計と分析における他のいくつかの問題では、二重指数列はアルゴリズムの分析ではなく、設計の中で使用されます。一例として、凸包を計算するためのチャンのアルゴリズムがあります。これは、テスト値h _i  = 2 ^{2 i} (最終的な出力サイズの推定値) を使用して一連の計算を実行し、シーケンス内の各テスト値にO( n  log  h _i ) の時間がかかります。これらのテスト値は二重指数関数的に増加するため、シーケンス内の各計算の時間はiの関数として単指数関数的に増加し、合計時間はシーケンスの最終ステップの時間によって支配されます。したがって、アルゴリズムの全体的な時間は O( n  log  h ) です。ここで、hは実際の出力サイズです。^[5]

いくつかの数論的境界は二重指数関数的である。n個の異なる素因数を持つ奇完全数は最大で であることが知られており、これはニールセン（2003）の結果である。^[6]${\displaystyle 2^{4^{n}}}$

k ≥ 1の内部格子点を持つd次元整数格子内の多面体の最大体積は、最大で

${\displaystyle k\cdot (8d)^{d}\cdot 15^{d\cdot 2^{2d+1}},}$

Pikhurko (2001)の結果。^[7]

電子時代における最大の素数は、ミラーとホイーラーが1951年にEDSAC 1で79桁の素数を発見して以来、おおよそ1年の二重指数関数で増加している。^[8]

人口動態では、人口増加は二重指数関数的であると想定されることがある。VarfolomeyevとGurevich ^[9]は実験的に

${\displaystyle N(y)=375.6\cdot 1.00185^{1.00737^{y-1000}}\,}$

ここで、N ( y )はy年の人口（百万人）です。

戸田振動子の自己脈動モデルでは、振幅の対数は時間とともに指数関数的に変化する（大きな振幅の場合）ため、振幅は時間の二重指数関数として変化する。^[10]

樹状高分子は二重指数関数的に成長することが観察されている。^[11]