時間計算量

理論計算機科学において、時間計算量とは、アルゴリズムの実行にかかる計算時間を表す計算量です。時間計算量は通常、アルゴリズムが実行する基本操作の数を数えることで推定されます。この場合、各基本操作の実行時間は一定であると仮定します。したがって、アルゴリズムの実行時間と基本操作の数は、定数倍で相関していると考えられます。

アルゴリズムの実行時間は、同じサイズの異なる入力間で異なる可能性があるため、通常は最悪の場合の時間計算量、つまり、特定のサイズの入力に必要な最大時間を考慮します。あまり一般的ではなく、通常は明示的に指定されるのは平均ケースの計算量、つまり、特定のサイズの入力にかかる時間の平均です (特定のサイズの可能な入力の数は限られているため、これは理にかなっています)。どちらの場合も、時間計算量は通常、入力のサイズの関数として表現されます。 ^[1]^{: 226}この関数を正確に計算するのは通常難しく、小さな入力の実行時間は通常は重要ではないため、通常は、入力サイズが増加したときの計算量の挙動、つまり計算量の漸近挙動に焦点が当てられます。したがって、時間計算量は通常、big O 記法、つまり、、、などを使用して表現されます。ここで、 $n$ は、入力を表すために必要なビット単位でのサイズです。 $O(n)$ $O(n\log n)$ $O(n^{\alpha })$ $O(2^{n})$

アルゴリズムの複雑性は、ビッグオー記法に現れる関数の種類によって分類されます。例えば、時間計算量を持つアルゴリズムは線形時間アルゴリズムであり、ある定数に対する時間計算量を持つアルゴリズムは多項式時間アルゴリズムです。 $O(n)$ $O(n^{\alpha })$ $\alpha >0$

一般的な時間計算量の表

次の表は、一般的に遭遇する時間計算量のいくつかのクラスをまとめたものである。表において、 $poly(x) = x O (1)$ 、すなわち xの多項式である。

定数時間

アルゴリズムの複雑さの値が入力のサイズに依存しない値で制限される場合、そのアルゴリズムは定数時間(時間とも表記される) であると言われます。たとえば、配列内の任意の 1 つの要素にアクセスする場合、その要素を見つけるには 1 つの操作のみを実行すればよいため、定数時間がかかります。同様に、昇順にソートされた配列で最小値を検索する場合、それは最初の要素です。ただし、順序付けられていない配列で最小値を検索する操作は、最小値を決定するために配列内の各要素をスキャンする必要があるため、定数時間ではありません。したがって、これは線形時間操作であり、時間がかかります。ただし、要素の数が事前にわかっていて、変更されない場合、そのようなアルゴリズムは定数時間で実行されると言えます。 ${\textstyle O(1)}$ ${\textstyle T(n)}$ ${\textstyle O(n)}$

「定数時間」という名前にもかかわらず、実行時間は必ずしも問題のサイズに依存しません。ただし、実行時間の上限は問題のサイズに依存しません。例えば、「必要であれば $a$ と $b$ の値を交換し、となるようにする」というタスクは、が既に真であるかどうかによって実行時間が左右される場合でも、定数時間と呼ばれます。ただし、必要な時間は常に最大で $t$ となるような定数 $t$ が存在します。 ${\textstyle a\leq b}$ ${\textstyle a\leq b}$

対数時間

アルゴリズムがのとき、対数時間がかかると言われます。とは定数乗数によって関連しており、このような乗数はビッグ O 分類とは無関係であるため、対数時間アルゴリズムの標準的な使用法は、 $T$ の式に現れる対数の底に関係なくです。 $T(n)=O(\log n)$ $\log _{a}n$ $\log _{b}n$ $O(\log n)$

対数時間を要するアルゴリズムは、バイナリツリーの操作やバイナリ検索の使用時によく見られます。

アルゴリズムは、 $nが$ 増加するにつれて演算回数と入力サイズの比率が減少し、ゼロに近づくほど効率的であると考えられます。入力のすべての要素にアクセスする必要があるアルゴリズムは、サイズ $n$ の入力を読み取るのにかかる時間が $n$ のオーダーであるため、対数的な時間をかけることはできません。 $O(\log n)$

対数時間の例として、辞書検索が挙げられます。n個 $の$ 項目がアルファベット順に並べられた辞書 $D$ を考えてみましょう。に対して、定数時間で辞書の $k$ 番目の項目にアクセスできるとします。この $k番目の項目をで表します。これらの仮定の下では、単語$ $w$ が辞書内に存在するかどうかを調べるテストは、対数時間で実行できます。を考えます。ここで、は床関数を表します。つまり、単語 $w$ が辞書のちょうど真ん中にある場合、これで完了です。そうでない場合、つまり単語 $w が$ 辞書全体で真ん中の単語よりもアルファベット順で前に来る場合、辞書の左半分（つまり、前の半分）で同じように検索を続け、正しい単語が見つかるまでこれを繰り返します。そうでない場合、つまり単語 w が真ん中の単語の後にある場合は、辞書の右半分で同様に続けます。このアルゴリズムは、紙の辞書で項目を見つけるときによく使用される方法に似ています。その結果、アルゴリズムが対象の単語に近づくにつれて、辞書内の検索空間は減少します。 $1\leq k\leq n$ $D(k)$ $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ $\lfloor \;\rfloor$ $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$

多重対数時間

あるアルゴリズムの実行時間が定数 $k$ であるとき、そのアルゴリズムは多重対数時間で実行されるといいます。これはとも表記されます。 $T(n)$ $O{\bigl (}(\log n)^{k}{\bigr )}$ $O(\log ^{k}n)$

例えば、行列連鎖の順序付けは並列ランダムアクセスマシン上で多重対数時間で解くことができ、^[7]、グラフが挿入/削除操作ごとに完全に動的な方法で平面であることを決定することができる。^[8] $O(\log ^{3}n)$

サブリニア時間

アルゴリズムがサブ線形時間（しばしばサブ線形時間と表記される）で実行されるとされるのは、の場合です。特に、これには上記で定義された時間計算量を持つアルゴリズムが含まれます。 $T(n)=o(n)$

サブ線形時間アルゴリズムという用語は、通常、入力のごく一部をサンプリングし、それを効率的に処理してインスタンス全体のプロパティを近似的に推測するランダム化アルゴリズムを指します。 ^[9]このタイプのサブ線形時間アルゴリズムは、プロパティテストと統計に密接に関連しています。

アルゴリズムをサブリニア時間で実行できるその他の設定は次のとおりです。

合計作業量が線形以上（入力全体を読み取ることができる）だが、深さが線形以下の並列アルゴリズム。
入力構造に関する仮定が保証されているアルゴリズム。重要な例としては、ソートされた配列における二分探索など、データ構造に対する演算が挙げられます。
入力の局所構造を探索するアルゴリズム。例えば、1次元配列の局所最小値を求めるアルゴリズム（二分探索の変種を用いることで短時間で解くことができる）。密接に関連する概念として、局所計算アルゴリズム（LCA）がある。これは、大きな入力を受け取り、有効な大きな出力に関する局所情報を照会するアルゴリズムである。^[10] $O(\log(n))$

線形時間

アルゴリズムの時間計算量がの場合、そのアルゴリズムは線形時間、またはかかると言われます。非公式には、これは実行時間が入力のサイズに比例して最大でも増加しないことを意味します。より正確には、サイズ $n$ のすべての入力に対して実行時間が最大でもとなるような定数 $c$ が存在することを意味します。例えば、リストのすべての要素を合計する手順は、追加時間が一定であるか、少なくとも定数で制限されている場合、リストの長さに比例した時間がかかります。 $O(n)$ $O(n)$ $cn$

線形時間は、アルゴリズムが入力全体を順次読み取る必要がある状況において、可能な限り最善の時間計算量です。そのため、線形時間、あるいは少なくとも線形時間に近いアルゴリズムを発見するための研究が数多く行われてきました。この研究には、ソフトウェアとハードウェアの両方の手法が含まれます。並列処理を利用してこれを実現するハードウェア技術はいくつかあります。例えば、連想メモリ（CAM）が挙げられます。この線形時間の概念は、ボイヤー・ムーア文字列検索アルゴリズムやウッコネンのアルゴリズムなどの文字列マッチングアルゴリズムで利用されています。

準線形時間

アルゴリズムは、ある正の定数 $k$ に対してであるとき、準線形時間（対数線形時間とも呼ばれる）で実行されると言われます。 ^[11]線形時間はの場合です。^[12]ソフト O 記法を使用すると、これらのアルゴリズムはとなります。準線形時間アルゴリズムは、任意の定数に対してであるため、任意のに対する項を含む時間制限を持つ多項式時間アルゴリズムよりも高速に実行されます。 $T(n)=O(n\log ^{k}n)$ $k=1$ ${\tilde {O}}(n)$ $O(n^{1+\varepsilon })$ $\varepsilon >0$ $n^{c}$ $c>1$

準線形時間で実行されるアルゴリズムには次のものがあります:

インプレースマージソート、 $O(n\log ^{2}n)$
クイックソート、のランダム化バージョンでは、最悪のケースの入力に対して期待値の範囲内の実行時間となります。ランダム化されていないバージョンでは、平均的なケースの複雑さを考慮した場合のみ、期待値の範囲内の実行時間となります。 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$
ヒープソート、マージソート、イントロソート、バイナリツリーソート、スムースソート、ペイシエントソートなど、最悪の場合 $O(n\log n)$
高速フーリエ変換、 $O(n\log n)$
モンジュ配列計算、 $O(n\log n)$

多くの場合、実行時間は単に操作を $n$ 回実行した結果です（表記法については、Big O表記法 § バッハマン・ランダウ表記法の族を参照してください）。例えば、二分木ソートは、 $n$ サイズの配列の各要素を1つずつ挿入することで二分木を作成します。自己平衡二分探索木への挿入操作には時間がかかるため、アルゴリズム全体に時間がかかります。 $O(n\log n)$ $\Theta (\log n)$ $O(\log n)$ $O(n\log n)$

比較ソートは、最悪の場合でも少なくとも回の比較を必要とします。これは、スターリング近似によりとなるためです。また、再帰関係からも頻繁に生じます。 $\Omega (n\log n)$ $\log(n!)=\Theta (n\log n)$ ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

サブ二次時間

アルゴリズムがサブ2乗時間であるとは、次の場合を指します。 $T(n)=o(n^{2})$

例えば、単純な比較ベースのソートアルゴリズムは二次式（例：挿入ソート）ですが、より高度なアルゴリズムの中には二次式以下のアルゴリズムもあります（例：シェルソート）。汎用ソートで線形時間で実行できるものはありませんが、二次式から二次式以下のアルゴリズムへの変更は実用上非常に重要です。

多項式時間

アルゴリズムの実行時間が、そのアルゴリズムの入力サイズに対する多項式式によって上限が定められている場合、そのアルゴリズムは多項式時間を持つと言われます。つまり、ある正の定数kに対してT ( n ) = O ( n ^k )となります。^[1]^[13]決定論的な多項式時間アルゴリズムが存在する問題は、計算複雑性理論の分野において中心的な複雑性クラスPに属します。コブハムのテーゼによれば、多項式時間は「扱いやすい」、「実行可能」、「効率的」、「高速」の同義語です。^[14]

多項式時間アルゴリズムの例:

n個の整数に対する選択ソートアルゴリズムは、定数Aに対する演算を実行する。したがって、このアルゴリズムは実行時間が非常に長く、多項式時間アルゴリズムである。 $An^{2}$ $O(n^{2})$
すべての基本的な算術演算 (加算、減算、乗算、除算、比較) は、多項式時間で実行できます。
グラフにおける最大マッチングは多項式時間で見つけることができます。特に最適化においては、強多項式時間アルゴリズムと弱多項式時間アルゴリズムを区別することがよくあります。

これら 2 つの概念は、アルゴリズムへの入力が整数で構成されている場合にのみ関連します。

複雑度クラス

多項式時間の概念は、計算複雑性理論においていくつかの複雑性クラスを導きます。多項式時間を用いて定義される重要なクラスには、次のようなものがあります。

P :決定性チューリングマシンで多項式時間で解ける決定問題の複雑さのクラス
NP :非決定性チューリングマシンで多項式時間で解ける決定問題の複雑さのクラス
ZPP ：確率チューリングマシンで多項式時間でゼロエラーで解ける決定問題の複雑さのクラス
RP : 確率的チューリングマシンで片側誤差で多項式時間で解決できる決定問題の複雑性クラス。
BPP : 確率チューリングマシン上で両側誤差を伴って多項式時間で解ける決定問題の複雑さのクラス
BQP :量子チューリングマシン上で多項式時間で両側誤差を伴って解ける決定問題の複雑さのクラス

P は、マシンモデルの変更に対して堅牢な決定論的マシンにおける最小の時間計算量クラスです。(例えば、単一テープチューリングマシンから複数テープマシンへの変更は、2乗の速度向上をもたらしますが、あるモデルで多項式時間で実行されるアルゴリズムは、他のモデルでも多項式時間で実行されます。) 任意の抽象マシンには、そのマシンで多項式時間で解ける問題に対応する計算量クラスがあります。

超多項式時間

T ( n ) がどの多項式によっても上界を持たなければ、つまり、すべての正の整数 $c$ に対して⁠ ⁠であれば、アルゴリズムは超多項式時間を取ると定義されます。 $T(n)\not \in O(n^{c})$

たとえば、サイズ $n$ の入力に対して $2 n$ ステップで実行されるアルゴリズムには、超多項式時間 (より具体的には、指数時間) が必要です。

指数リソースを使用するアルゴリズムは明らかに超多項式ですが、一部のアルゴリズムは非常に弱い超多項式に過ぎません。例えば、Adleman–Pomerance–Rumely素数判定は、 $nビット入力に対して$ $n O (log log n)$ 回実行されます。これは、 $nが$ 十分に大きい場合、どの多項式よりも速く増加しますが、入力サイズが実用的ではないほど大きくなると、低次数の多項式によって支配されなくなります。

超多項式時間を必要とするアルゴリズムは、計算量クラス Pの範囲外にあります。コブハムのテーゼは、これらのアルゴリズムは非実用的であると仮定しており、多くの場合、実際そうなっています。P対NP問題は未解決であるため、 NP完全問題が超多項式時間を必要とするかどうかは不明です。

準多項式時間

準多項式時間アルゴリズムとは、実行時間が準多項式増加を示すアルゴリズムです。これは、多項式時間より遅くなる場合もありますが、指数時間よりは大幅に高速な動作の一種です。準多項式時間アルゴリズムの最悪実行時間は、ある固定値の場合です。この場合は多項式時間となり、の場合は線形以下の時間となります。 $2^{O(\log ^{c}n)}$ $c>0$ $c=1$ $c<1$

準多項式時間アルゴリズムは知られているものの、多項式時間アルゴリズムは知られていない問題がいくつかあります。このような問題は近似アルゴリズムで発生します。有名な例としては、有向シュタイナー木問題が挙げられます。この問題には、近似係数n （nは頂点数）を達成する準多項式時間近似アルゴリズムが存在します。しかし、そのような多項式時間アルゴリズムの存在を示すことは未解決の問題です。 $O(\log ^{3}n)$

準多項式時間解を持つが多項式時間解が知られていない他の計算問題には、クリークとランダムグラフの和集合から大きなクリークを見つけることを目的とする植え付けクリーク問題がある。植え付けクリーク問題は準多項式的に解けるものの、多項式時間解を持たないと予想されてきた。この植え付けクリーク予想は、計算ゲーム理論、特性検定、機械学習における他のいくつかの問題の計算困難性を証明するための計算困難性仮定として用いられてきた。^[15]

計算量クラスQPは、準多項式時間アルゴリズムを持つすべての問題から構成されます。これはDTIMEを用いて以下のように定義できます。^[16]

{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)

NP完全問題との関係

複雑性理論において、未解決のP対NP問題は、NPにおけるすべての問題に多項式時間アルゴリズムが存在するかどうかを問うものです。3SATなど、 NP完全問題に対する最もよく知られたアルゴリズムはすべて指数時間かかります。実際、多くの自然なNP完全問題には、指数時間未満のアルゴリズムは存在しないと推測されています。ここで「指数時間未満」とは、以下に示す2番目の定義を指します。（一方、隣接行列によって自然に表現される多くのグラフ問題は、入力のサイズが頂点数の2乗であるという理由だけで、指数時間未満で解くことができます。）この推測（k-SAT問題の場合）は、指数時間仮説として知られています。^[17] NP完全問題には準多項式時間アルゴリズムが存在しないと推測されているため、近似アルゴリズムの分野におけるいくつかの近似不可能性の結果は、 NP完全問題には準多項式時間アルゴリズムが存在しないという仮定に基づいています。例えば、集合被覆問題における既知の近似不可能性の結果を参照してください。

指数関数以下の時間

指数関数的時間未満という用語は、あるアルゴリズムの実行時間が任意の多項式よりも速く増加する可能性があるものの、指数関数的時間よりは大幅に短いことを表すために使用されます。この意味で、指数関数的時間未満アルゴリズムを含む問題は、指数関数的アルゴリズムのみを含む問題よりもいくらか扱いやすいと言えます。「指数関数的」の正確な定義は一般的には一致していませんが^[18]、最も広く使用されている2つの定義を以下に示します。

最初の定義

ある問題が、与えられた多項式よりも対数が小さくなる実行時間で解ける場合、その問題は指数時間未満で解けると言われる。より正確には、すべてのε > 0に対して、その問題をO (2 ^{n ^ε} )の時間で解くアルゴリズムが存在する場合、その問題は指数時間未満である。このような問題全体の集合は、計算量クラスSUBEXPであり、これは以下のようにDTIMEを用いて定義される。^[6]^[19]^[20]^[21]

{\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)

この部分指数の概念は、 ε が入力の一部ではなく、各 ε が問題に対して独自のアルゴリズムを持つ可能性があるという意味で、εに関して非均一です。

2番目の定義

一部の研究者は、指数関数的未満時間をの実行時間と定義しています。^[17]^[22]^[23]この定義では、指数関数的未満時間の最初の定義よりも大きな実行時間が許容されます。このような指数関数的未満時間アルゴリズムの例として、最もよく知られている古典的な整数因数分解アルゴリズムである一般数体ふるいが挙げられます。これは、入力の長さが $nのとき$ 、約の時間で実行されます。もう 1 つの例として、グラフ同型性問題が挙げられます。これは、1982 年から 2016 年までの間に最もよく知られたアルゴリズムによってで解かれました。しかし、STOC 2016 では、準多項式時間アルゴリズムが発表されました。^[24] $2^{o(n)}$ $2^{{\tilde {O}}(n^{1/3})}$ $2^{O\left({\sqrt {n\log n}}\right)}$

アルゴリズムがインスタンスのサイズ、頂点数、または辺数に関して指数関数的以下になることを許容するかどうかは、アルゴリズムの性能に影響を及ぼす。パラメータ化された複雑性においては、この違いは、決定問題とパラメータkのペアを考慮することで明確に示される。SUBEPTは、 kに関して指数関数的以下かつ入力サイズnに関して多項式的な時間で実行されるすべてのパラメータ化された問題のクラスである。[ ^25] $(L,k)$

{\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).

より正確には、SUBEPT は、の計算可能な関数と、時間でL を決定するアルゴリズムが存在するすべてのパラメーター化された問題のクラスです。 $(L,k)$ $f:\mathbb {N} \to \mathbb {N}$ $f\in o(k)$ $2^{f(k)}\cdot {\textsf {poly}}(n)$

指数時間仮説

指数時間仮説( ETH ) は、3SAT、つまり、節ごとに最大 3 つのリテラルとn 個の変数を持つ連言正規形のブール式の充足可能性問題が、時間 2 ^o⁽ⁿ⁾で解くことができないというものである。より正確には、この仮説は、絶対定数 $c$ $> 0が存在し、3SAT は任意の決定論的チューリングマシンによって時間 2$ ^cnで決定できないというものである。mを節の数を表すと、 ETH は、任意の整数 $k$ $\geq 3に対して$ k SAT は時間 2 ^o⁽^m⁾で解くことができないという仮説と同等である。^[26]指数時間仮説はP ≠ NP を意味する。

指数時間

T ( n ) が 2 ^poly(ⁿ⁾ （ poly( n ) はnの何らかの多項式）で上限となるとき、アルゴリズムは指数時間であるといわれます。より正式には、ある定数kに対してT ( n ) がO (2 ⁿ^{^k} )で上限となるとき、アルゴリズムは指数時間です。決定性チューリングマシン上で指数時間アルゴリズムが実行可能な問題は、 EXPと呼ばれる計算量クラスを形成します。

{\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)

指数時間は、 T ( n ) = 2 ^{O ( n )}を満たすアルゴリズムを指すために使用されることがあります。ここで、指数は最大でnの線形関数です。これにより、計算量クラスはEになります。

{\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)

階乗時間

T(n)が階乗関数n!の上限を持つ場合、アルゴリズムは階乗時間であると言われます。階乗時間は、すべてのに対してとなるため、指数時間 (EXP) の部分集合です。しかし、E の部分集合ではありません。 $n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)$ $\epsilon >0$

階乗時間で実行されるアルゴリズムの例として、試行錯誤に基づく悪名高い非効率なソートアルゴリズムであるボゴソートが挙げられます。ボゴソートは、n個の項目からなるリストを繰り返しシャッフルすることで、ソートが完了していると判断されるまでソートします。平均的なケースでは、ボゴソートアルゴリズムを実行するたびに、 n個の項目のn !通りの順序のいずれかが検査されます。項目が異なる場合、そのような順序は1つだけソートされます。ボゴソートは、無限サル定理と共通の原理を持っています。

二重指数時間

あるアルゴリズムが二重指数時間であるとは、T ( n ) の上限が 2 ^{2 ^{poly( n )}}（ poly( n ) はnの任意の多項式）であるときである。このようなアルゴリズムは計算量クラス2-EXPTIMEに属する。

{\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)

よく知られている二重指数時間アルゴリズムには以下のものがあります。

プレスブルガー算術の決定手順
グレブナー基底の計算（最悪の場合^[27]）
実閉体上の量指定子除去は少なくとも二重指数時間かかり^[28]、この時間で実行できる。^[29]

参照

参考文献

^ ab シプサー、マイケル(2006).計算理論入門. Course Technology Inc. ISBN 0-619-21764-2。
^ Mehlhorn, Kurt ; Naher, Stefan (1990). 「 $O$ $(log log$ $N$ $)$ 時間と $O$ $($ $n$ $)$ の空間で実現される有界順序付き辞書」.情報処理レター. 35 (4): 183– 189. doi :10.1016/0020-0190(90)90022-P.
^ タオ, テレンス(2010). 「1.11 AKS素数判定」.余白のイプシロン II: 数学ブログ3年目のページ. 数学大学院研究. 第117巻. プロビデンス, ロードアイランド州: アメリカ数学会. pp. 82– 86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010。
^ Lenstra, HW Jr. ; Pomerance, Carl (2019). 「ガウス周期による素数判定」(PDF) .欧州数学会誌. 21 (4): 1229– 1269. doi :10.4171/JEMS/861. hdl :21.11116/0000-0005-717D-0. MR 3941463. S2CID 127807021.
^ Calude, Cristian S.、Jain, Sanjay、Khoussainov, Bakhadyr、Li, Wei、Stephan, Frank (2017). 「準多項式時間でのパリティゲームの決定」第49回ACM SIGACT計算理論シンポジウム議事録. Association for Computing Machinery. pp. 252– 263. doi :10.1145/3055399.3055409. hdl :2292/31757. ISBN 9781450345286. S2CID 30338402。{{cite book}}: CS1 maint: multiple names: authors list (link)
^ ab Babai, László ; Fortnow, Lance ; Nisan, N. ; Wigderson, Avi (1993). 「EXPTIMEに出版可能な証明がない限り、BPPは指数関数以下の時間シミュレーションを実行する」.計算複雑性. 3 (4). ベルリン、ニューヨーク: Springer-Verlag : 307– 318. doi :10.1007/BF01275486. S2CID 14802332.
^ Bradford, Phillip G.; Rawlins, Gregory JE; Shannon, Gregory E. (1998). 「ポリログ時間における効率的な行列チェーン順序付け」. SIAM Journal on Computing . 27 (2): 466– 490. doi :10.1137/S0097539794270698. MR 1616556.
^ Holm, Jacob; Rotenberg, Eva (2020). 「対数時間で完全動的平面性テスト」. Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (編). Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 . Association for Computing Machinery. pp. 167– 180. arXiv : 1911.03449 . doi :10.1145/3357713.3384249. ISBN 978-1-4503-6979-4。
^ Kumar, Ravi; Rubinfeld, Ronitt (2003). 「亜線形時間アルゴリズム」(PDF) . SIGACT News . 34 (4): 57– 67. doi :10.1145/954092.954103. S2CID 65359.
^ Rubinfeld, Ronitt (2019). 「ローカル計算アルゴリズム」. 2019 ACM Symposium on Principles of Distributed Computing Proceedings . p. 3. doi :10.1145/3293611.3331587. ISBN 978-1-4503-6217-7。
^ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). 「準線形時間計算量理論について」(PDF) .理論計算機科学. 148 (2): 325– 349. doi : 10.1016/0304-3975(95)00031-Q . MR 1355592.
^ セジウィック, ロバート; ウェイン, ケビン (2011). 『アルゴリズム』（第4版）. ピアソン・エデュケーション. p. 186.
^ パパディミトリウ, クリストス・H. (1994).計算複雑性. マサチューセッツ州レディング: アディソン・ウェスレー. ISBN 0-201-53082-1。
^ コブハム、アラン(1965). 「関数の本質的な計算困難さ」. Proc. Logic, Methodology, and Philosophy of Science II . ノースホランド.
^ Braverman, Mark ; Kun-Ko, Young ; Rubinstein, Aviad ; Weinstein, Omri (2017). 「完全完全性を持つ最密 $k部分グラフのETH困難性」. Klein, Philip N. (編).$ 第28回ACM-SIAM離散アルゴリズムシンポジウム議事録, SODA 2017, バルセロナ, スペイン, Hotel Porta Fira, 1月16-19日. Society for Industrial and Applied Mathematics. pp. 1326– 1341. arXiv : 1504.08352 . doi :10.1137/1.9781611974782.86. ISBN 978-1-61197-478-2. MR 3627815。
^ 複雑性動物園：クラスQP：準多項式時間
^ ab Impagliazzo, Russell ; Paturi, Ramamohan (2001). 「k-SATの複雑性について」(PDF) . Journal of Computer and System Sciences . 62 (2): 367– 375. doi : 10.1006/jcss.2000.1727 . MR 1820597.
^ Aaronson, Scott (2009年4月5日). 「指数関数的ではないジレンマ」. Shtetl-Optimized . 2009年12月2日閲覧。
^ 複雑性動物園：クラス SUBEXP：決定論的準指数時間
^ Moser, P. (2003). 「小さな計算量クラスにおけるBaireのカテゴリー」. Andrzej Lingas; Bengt J. Nilsson (編).計算理論の基礎：第14回国際シンポジウム、FCT 2003、スウェーデン、マルメ、2003年8月12日～15日、議事録.コンピュータサイエンス講義ノート. 第2751巻. ベルリン、ニューヨーク：Springer-Verlag. pp. 333– 342. doi :10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.
^ Miltersen, PB (2001). 「Derandomizing Complexity Classes」.ランダム化コンピューティングハンドブック. 組み合わせ最適化. 第9巻. Kluwer Academic Pub. p. 843. doi :10.1007/978-1-4615-0013-1_19 (2025年7月21日現在非アクティブ). ISBN 978-1-4613-4886-3。{{cite book}}: CS1 maint: DOI inactive as of July 2025 (link)
^ Kuperberg, Greg (2005). 「二面体隠れ部分群問題に対する準指数時間量子アルゴリズム」. SIAM Journal on Computing . 35 (1). フィラデルフィア: 188. arXiv : quant-ph/0302112 . doi :10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.
^ Oded Regev (2004). 「多項式空間における二面体隠れ部分群問題に対する準指数時間アルゴリズム」arXiv : quant-ph/0406151v1 .
^ Grohe, Martin; Neuen, Daniel (2021). 「グラフ同型性問題に関する最近の進歩」. Dabrowski, Konrad K.; Gadouleau, Maximilien; Georgiou, Nicholas; Johnson, Matthew; Mertzios, George B.; Paulusma, Daniël (編). Surveys in combinatorics 2021 . ロンドン数学会講演ノートシリーズ. 第470巻. ケンブリッジ大学出版局. pp. 187– 234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3. MR 4273431。
^ フルム、ヨルグ;グローエ、マーティン(2006)。パラメータ化された複雑性理論。スプリンガー。 p. 417.ISBN 978-3-540-29952-3。
^ Impagliazzo, R. ; Paturi, R. ; Zane, F. (2001). 「どの問題が強く指数関数的な複雑性を持つか？」Journal of Computer and System Sciences . 63 (4): 512– 530. doi : 10.1006/jcss.2001.1774 .
^ Mayr, Ernst W. ; Meyer, Albert R. (1982). 「可換半群と多項式イデアルに関する語句問題の複雑さ」. Advances in Mathematics . 46 (3): 305– 329. doi : 10.1016/0001-8708(82)90048-2 . hdl : 1721.1/149010 . MR 0683204.
^ Davenport, James H. ; Heintz, Joos (1988). 「実数量子除去は二重指数関数的である」. Journal of Symbolic Computation . 5 ( 1–2 ): 29– 35. doi : 10.1016/S0747-7171(88)80004-X . MR 0949111.
^ Collins, George E. (1975). 「円筒代数分解による実閉体に対する量指定子除去」 Brakhage, H. (編).オートマトン理論と形式言語：第2回GI会議、カイザースラウテルン、1975年5月20～23日. コンピュータサイエンス講義ノート. 第33巻. Springer. pp. 134– 183. doi : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6. MR 0403962。