時間の複雑さ

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
アルゴリズムの分析で一般的に使用される関数のグラフ。各関数の操作数Nと入力サイズnを示しています。

コンピュータサイエンスでは時間計算量は、アルゴリズムの実行にかかるコンピュータ時間の量を表す計算量です。時間計算量は、通常、アルゴリズムによって実行される基本操作の数を数えることによって推定されます。各基本操作の実行には一定の時間がかかると想定しています。したがって、かかる時間とアルゴリズムによって実行される基本操作の数は、一定の係数によって関連付けられると見なされます。

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

アルゴリズムの複雑さは、ビッグO表記に現れる関数のタイプに従って分類されます。たとえば、時間計算量のあるアルゴリズム線形時間アルゴリズムであり、時間計算量のあるアルゴリズムです。一定の定数多項式時間アルゴリズムです。

一般的な時間計算量の表

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

名前 複雑さのクラス 実行時間(Tn)) 実行時間の例 アルゴリズムの例
一定時間 O(1) 10 並べ替えられた数値 の配列で中央値を見つける

(-1)nの計算

逆アッカーマン時間 Oαn)) 素集合を使用した操作ごとの償却時間
反復対数時間 Olog *  n サイクルの分散カラーリング
対数-対数 O(ログログn 制限付き優先キューを使用した操作ごとの償却時間[2]
対数時間 DLOGTIME O(log  n log  n、log(n 2 二分探索
多対数時間 poly(log  n (log  n2
分数パワー On cここで、 0 < c <1 n 1/2n 2/3 kdツリーでの検索
線形時間 On n、2 n + 5 ソートされていない配列内の最小または最大のアイテムの検索Kadaneのアルゴリズム線形検索
「nlog-starn」時間 On log * n Seidelポリゴン三角分割アルゴリズム。
線形時間 On log n n log n log n 可能な限り最速の比較ソート; 高速フーリエ変換
準線形時間 n poly(log n
二次時間 On 2 n 2 バブルソート; 挿入ソート; 直接畳み込み
立方時間 On 3 n 3 2つのn × n行列の素朴な乗算。偏相関の計算
多項式時間 P 2 O(log n = poly(n n 2 + nn 10 線形計画法のためのカーマーカーのアルゴリズム; AKS素数性テスト[3] [4]
準多項式時間 QP 2 poly(log  n n ログログ nnログn 最もよく知られているO(log 2 n)-有向シュタイナー木問題の近似アルゴリズム
サブ指数時間
(最初の定義)
SUBEXP すべてのε > 0に対してO2nε ) EXPTIME(以下を参照)がMAと等しくない限り、 BPPが含まれます[5]
サブ指数時間
(秒の定義)
2 on 2 n 1/3 素因数分解の最もよく知られたアルゴリズム; グラフ同型のための以前の最良のアルゴリズム
指数時間
(線形指数を使用)
E 2 On 1.1 n、10 n 動的計画法を使用して巡回セールスマン問題を解決する
指数関数的な時間 EXPTIME 2 poly(n 2 n、2 n 2 ブルートフォース検索による行列の連鎖乗積の解決
階乗時間 On!) n ブルートフォース検索による巡回セールスマン問題の解決
二重指数時間 2-EXPTIME 2 2 poly(n 2 2 n プレスバーガー算術で与えられたステートメントの真実を決定する

一定時間

Tn)の値が入力のサイズに依存しない値によって制限されている場合、アルゴリズムは定数時間O(1)時間とも表記)と呼ばれます。たとえば、配列内の任意の1つの要素にアクセスするには、その要素を見つけるために1つの操作を実行するだけでよいため、一定の時間がかかります。同様の方法で、昇順で並べ替えられた配列の最小値を見つけます。それは最初の要素です。ただし、順序付けされていない配列で最小値を見つけることは、最小値を決定するために配列内の各要素をスキャンする必要があるため、定数時間の操作ではありません。したがって、これは線形時間演算であり、Oを取りますn)時間。ただし、要素の数が事前にわかっていて変化しない場合でも、そのようなアルゴリズムは一定時間で実行されていると言えます。

「一定時間」という名前にもかかわらず、実行時間は問題のサイズに依存しない必要がありますが、実行時間の上限は問題のサイズに依存しないようにする必要があります。たとえば、タスク「必要に応じてaとbの値を交換して、a≤bになるようにする a≤bすでに真であるかどうかによって時間が異なる場合でも、一定時間と呼ばれますただし、必要な時間は常に最大でtになるように、一定のtがあります。

一定時間で実行されるコードフラグメントの例を次に示します。

intインデックス= 5;
int item = list [index];
if(条件true)then
    一定時間で実行されるいくつかの操作を実行します
そうしないと
    一定時間で実行される他の操作を実行する
i = 1〜100
    場合j = 1〜200場合
        一定時間で実行されるいくつかの操作を実行します

Tn)がO任意の定数値)の場合、これはTn)がO(1)であると同等であり、標準表記で示されます。

対数時間

Tn)= O(log nの場合、アルゴリズムは対数時間を要すると言われています。log anとlogb n定数乗数によって関連付けられ、そのような乗数はbig-O分類とは無関係であるため、対数時間アルゴリズムの標準的な使用法は、対数の底に関係なくO(log n)です。Tの式  

対数時間をとるアルゴリズムは、一般に、二分木での操作または二分探索を使用する場合に見られます。

O(log n )アルゴリズムは、入力のサイズに対する操作の数の比率が減少し、 nが増加するとゼロになる傾向があるため、非常に効率的であると見なされます入力のすべての要素にアクセスする必要があるアルゴリズムは、サイズnの入力の読み取りにかかる時間がnのオーダーであるため、対数時間をとることはできません

対数時間の例は、辞書検索によって与えられます。アルファベット順にソートされたn個のエントリを含む辞書 Dについて考えてみます1≤k≤nの場合、辞書のk番目のエントリに一定時間でアクセスできる仮定します。D kがこのk番目のエントリを表すとします。これらの仮説の下で、単語wが辞書にあるかどうかを確認するテストは、対数時間で実行できます。ここで床関数を示しますもしもこれで完了です。それ以外の場合、辞書の左半分で同じ方法で検索を続行します。それ以外の場合は、辞書の右半分で同様に続行します。このアルゴリズムは、紙の辞書でエントリを見つけるためによく使用される方法に似ています。

多対数時間

アルゴリズムは、その時間Tnある定数kに対してO((log nk)である場合、対数時間で実行されると言われます。これを書く別の方法はO(log k nです。

たとえば、行列の連鎖順序は、並列ランダムアクセスマシンで多対数時間で解くことができ[6]グラフは、挿入/削除操作ごとのO(log 3 n )時間で完全に動的な方法で平面であると判断できます。[7]

劣線形時間

Tn)= onの場合、アルゴリズムは劣線形時間(多くの場合、線形時間と綴られる)で実行されると言われます特に、これには上記で定義された時間計算量のアルゴリズムが含まれます。

正確でありながらサブリニア時間で実行される一般的なアルゴリズムは、並列処理を使用するか(NC 1行列式の計算と同様)、あるいは入力構造についての仮定を保証します(対数時間二分探索や多くのツリー保守アルゴリズムと同様)。 。ただし、文字列の最初のlog( n )ビットで示される位置に1ビットがあるすべての文字列のセットなどの形式言語は、入力のすべてのビットに依存し、劣線形時間で計算できる場合があります。

特定の用語の劣線形時間アルゴリズムは、通常、従来のシリアルマシンモデルで実行され、入力に対する事前の仮定が許可されていないという点で、上記とは異なるアルゴリズムに予約されています。[8]ただし、それらはランダム化することが許可されており、実際、最も些細なタスクを除くすべてのタスクに対してランダム化する必要があります。

このようなアルゴリズムは、入力全体を読み取らずに答えを提供する必要があるため、その詳細は、入力に許可されているアクセスに大きく依存します。通常、バイナリ文字列b 1、…、b kとして表される入力の場合、アルゴリズムは時間O (1 で任意のiのbiの値を要求して取得できると想定されます。

劣線形時間アルゴリズムは通常ランダム化されており、近似解のみを提供します。実際、ゼロのみ(および1なし)のバイナリ文字列のプロパティは、(非近似の)劣線形時間アルゴリズムでは決定できないことが簡単に証明できます。劣線形時間アルゴリズムは、特性試験の調査で自然に発生します。

線形時間

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

線形時間は、アルゴリズムが入力全体を順次読み取る必要がある状況で、可能な限り最良の時間計算量です。したがって、線形時間または少なくともほぼ線形時間を示すアルゴリズムを発見するために多くの研究が投資されてきました。この調査には、ソフトウェアとハ​​ードウェアの両方の方法が含まれます。これを提供するために並列処理を利用するいくつかのハードウェアテクノロジがあります例として、連想メモリがあります。この線形時間の概念は、Boyer–MooreアルゴリズムUkkonenのアルゴリズムなどの文字列照合アルゴリズムで使用されます。

準線形時間

ある正の定数kに対してTn)= On log k nの場合、アルゴリズムは準線形時間(対数線形時間とも呼ばれます)で実行されると言われます[9]線形時間k = 1の場合です。[10]ソフトO表記を使用すると、これらのアルゴリズムはÕ(n)になります。準線形時間アルゴリズムも、すべての定数ε > 0に対してOn 1 + ε )です。 したがって、時間限界に任意のc > 1のncが含まれる多項式時間アルゴリズムよりも高速に実行されます

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

多くの場合、n log nの実行時間は、単にΘ(log n)操作をn回実行した結果です(表記については、Big O表記§Bachmann–Landau表記のファミリーを参照してください)。たとえば、二分木ソートは、 nサイズの配列の各要素を1つずつ挿入することによって二分木を作成します。自己平衡二分探索木の挿入操作にO(log n)時間がかかるため、アルゴリズム全体にはOn log n時間がかかります。

スターリングの近似によるlog(n!)=Θ(n log nであるため、最悪の場合、比較ソートには少なくともΩ(n log n )の比較が必要です。それらはまた、漸化式Tn)= 2 Tn / 2)+ Onから頻繁に発生します。

サブ二次時間

Tn)= on 2場合、アルゴリズムは準二次時間であると言われます

たとえば、単純な比較ベースのソートアルゴリズムは二次式(挿入ソートなど)ですが、二次式以下のより高度なアルゴリズム(シェルソートなど)を見つけることができます。線形時間で実行される汎用ソートはありませんが、2次からサブ2次への変更は実用上非常に重要です。

多項式時間

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

多項式時間アルゴリズムのいくつかの例:

  • n個の整数に対する選択ソートソートアルゴリズムは、ある定数Aの演算。したがって、それは時間内に実行されますとは多項式時間アルゴリズムです。
  • すべての基本的な算術演算(加算、減算、乗算、除算、および比較)は、多項式時間で実行できます。
  • グラフの最大一致、多項式時間で見つけることができます。

強くも弱くも多項式時間

一部のコンテキスト、特に最適化では、強多項式時間アルゴリズムと弱多項式時間アルゴリズムを区別します。これらの2つの概念は、アルゴリズムへの入力が整数で構成されている場合にのみ関係します。

強力な多項式時間は、計算の算術モデルで定義されます。この計算モデルでは、基本的な算術演算(加算、減算、乗算、除算、および比較)は、オペランドのサイズに関係なく、実行するために単位時間ステップを取ります。次の場合、アルゴリズムは強力な多項式時間で実行されます。[13]

  1. 計算の算術モデルの演算数は、入力インスタンスの整数数の多項式によって制限されます。
  2. アルゴリズムで使用されるスペースは、入力のサイズの多項式によって制限されます。

これらの2つのプロパティを持つアルゴリズムは、チューリングマシンで算術演算を実行するための適切なアルゴリズムで算術演算を置き換えることにより、多項式時間アルゴリズムに変換できます。2番目の条件は厳密に必要です:整数が与えられた場合(チューリングマシンモデルではnに比例するスペースを占める)、計算することが可能です繰り返し二乗を使用してn回乗算します。ただし、表現に使用されるスペースに比例します、したがって、入力を表すために使用される空間では、多項式ではなく指数関数になります。したがって、チューリングマシンでは多項式時間でこの計算を実行することはできませんが、多項式的に多くの算術演算で計算することはできます。

ただし、最初の条件では、バイナリエンコードされた入力の長さの多項式で囲まれたいくつかのチューリングマシンステップで実行されるアルゴリズムがありますが、入力の数の多項式で囲まれた多くの算術演算は実行されません。数字。2つの整数の最大公約数を計算するためユークリッドアルゴリズムはその一例です。与えられた2つの整数、アルゴリズムは実行しますせいぜい数の算術演算ビット。同時に、算術演算の数は、入力の整数の数によって制限することはできません(この場合は一定であり、入力には常に2つの整数しかありません)。後者の観察により、アルゴリズムは強力な多項式時間では実行されません。その実際の実行時間は、対数的に次の大きさに依存します。(つまり、ビット単位の長さ)であり、入力の整数の数だけではありません。

多項式時間で実行されるが、強く多項式ではないアルゴリズムは、弱多項式時間で実行されると言われます[14] 弱い多項式時間アルゴリズムは知られているが、強い多項式時間アルゴリズムを認めることは知られていない問題のよく知られた例は、線形計画法です。弱多項式時間は、問題の値の大きさに線形に依存し、真の多項式時間ではない 疑似多項式時間と混同しないでください。

複雑さのクラス

多項式時間の概念は、計算の複雑さの理論におけるいくつかの複雑さのクラスにつながります。多項式時間を使用して定義されたいくつかの重要なクラスは次のとおりです。

P 多項式時間で 決定論的チューリングマシン解決できる決定問題複雑さクラス
NP 非決定性チューリングマシンで多項式時間 で解くことができる決定問題の複雑さのクラス
ZPP 多項式時間で 確率的チューリングマシンでゼロエラーで解決できる決定問題の複雑度クラス
RP 多項式時間で確率的チューリングマシンの片側誤差で解決できる決定問題の複雑さのクラス。
BPP 多項式時間で確率的チューリングマシンの両側誤差で解決できる決定問題の複雑度クラス
BQP 多項式時間で の量子チューリングマシンの両側誤差で解決できる決定問題の複雑度クラス

Pは、決定論的マシンで最小の時間計算量クラスであり、マシンモデルの変更に関して堅牢です。(たとえば、シングルテープチューリングマシンからマルチテープマシンに変更すると、2次高速化につながる可能性がありますが、一方のモデルで多項式時間で実行されるアルゴリズムは、もう一方のモデルでも同様に実行されます)そのマシンで多項式時間で解くことができる問題に対応する複雑さのクラスを持っています。

超多項式時間

Tn)がどの多項式によっても制限されていない場合、アルゴリズムは超多項式時間を要すると言われます。小さなオメガ表記を使用すると、すべての定数cのωn c )時間になります。ここで、nは入力パラメーター、通常は入力のビット数です。

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

指数リソースを使用するアルゴリズムは明らかに超多項式ですが、一部のアルゴリズムは非常に弱い超多項式にすぎません。たとえば、Adleman-Pomerance-Rumely素数性テストは、nビット入力でn O(log log n時間実行されます。これは、 nが十分に大きい場合、どの多項式よりも速く成長しますが、入力サイズは、次数が小さい多項式で支配できなくなる前に、非現実的に大きくなる必要があります。

超多項式時間を必要とするアルゴリズムは、複雑度クラス Pの外側にあります。Cobhamの論文は、これらのアルゴリズムは実用的ではなく、多くの場合、実用的ではないと主張しています。P対NP問題は未解決であるため、 NP完全問題が超多項式時間を必要とする かどうかは不明です。

準多項式時間

準多項式時間アルゴリズムは、多項式時間より長く実行されますが、指数時間ほど長くは実行されないアルゴリズムです。準多項式時間アルゴリズムの最悪の場合の実行時間は次のとおりです。一部の固定ために多項式時間アルゴリズムを取得します。劣線形時間アルゴリズムを取得します。

準多項式時間アルゴリズムは、通常NP困難な問題から別の問題への縮小で発生します。たとえば、3SATなどのNP困難問題のインスタンスを取得し、それを別の問題Bのインスタンスに変換できますが、インスタンスのサイズは次のようになります。その場合、この削減は問題BがNP困難であることを証明しません。この削減は、3SAT(したがってすべてのNP )の準多項式時間アルゴリズムがない限り、Bの多項式時間アルゴリズムがないことを示しているだけです同様に、準多項式時間アルゴリズムがわかっている問題がいくつかありますが、多項式時間アルゴリズムはわかっていません。このような問題は、近似アルゴリズムで発生します。有名な例は、有向シュタイナー木問題です。この問題には、次の近似係数を達成する準多項式時間近似アルゴリズムがあります。nは頂点の数です)が、そのような多項式時間アルゴリズムの存在を示すことは未解決の問題です。

準多項式時間解に関する他の計算問題は、既知の多項式時間解ではなく、クリークとランダムグラフの和集合で大きなクリークを見つけることが目標である植え付けクリーク問題を含みます。準多項式的に解くことができますが、植え付けられたクリーク問題には多項式時間の解がないと推測されています。この植え付けられたクリークの推測は、計算ゲーム理論特性試験機械学習における他のいくつかの問題の難しさを証明するための計算難度の仮定として使用されています。[15]

複雑度クラスQPは、準多項式時間アルゴリズムを持つすべての問題で構成されます。DTIMEで次のように定義できます。[16]

NP完全問題との関係

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

サブ指数時間

サブ指数時間という用語は、あるアルゴリズムの実行時間がどの多項式よりも速く成長する可能性があるが、それでも指数よりも大幅に小さいことを表すために使用されます。この意味で、指数以下の時間アルゴリズムを持つ問題は、指数アルゴリズムしかない問題よりもいくらか扱いやすくなります。「サブ指数」の正確な定義は一般的に合意されておらず[18]、以下に最も広く使用されている2つをリストします。

最初の定義

問題は、対数が任意の多項式よりも小さくなる実行時間で解決できる場合、指数関数以下の時間で解決可能であると言われます。より正確には、すべてのε > 0に対して、時間O2nε )で問題を解決するアルゴリズムが存在する場合、問題は指数関数以下の時間にありますこのようなすべての問題のセットは、次のようにDTIMEで定義できる複雑度クラスSUBEXPです。[5] [19] [20] [21]

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

2番目の定義

一部の作成者は、指数以下の時間を2 onの実行時間として定義しています[17] [22] [23]この定義により、サブ指数時間の最初の定義よりも長い実行時間が可能になります。このようなサブ指数時間アルゴリズムの例は、素因数分解のための最もよく知られている古典的なアルゴリズムである一般的な数体ふるいです。ここで、入力の長さはnです。もう1つの例は、グラフ同型問題でした。これは、1982年から2016年までの最もよく知られたアルゴリズムで解決されました。ただし、STOC 2016では、準多項式時間アルゴリズムが提示されました。[24]

アルゴリズムがインスタンスのサイズ、頂点の数、またはエッジの数でサブ指数関数であることが許可されているかどうかによって違いが生じます。パラメータ化された複雑性では、この違いはペアを考慮することで明確になります決定問題とパラメータkSUBEPTは、 kでサブ指数関数的に実行され、入力サイズnで多項式で実行されるすべてのパラメーター化された問題のクラスです:[25]

より正確には、SUBEPTはすべてのパラメーター化された問題のクラスです計算可能な関数があります そして時間内にLを決定するアルゴリズム

指数時間仮説

指数時間仮説ETH)は、3SAT 、つまり、句ごとに最大3つのリテラルとn個の変数を持つ連言標準形のブール式の充足可能性問題は時間2 onでは解決できないというものです。より正確には、3SATが決定論的チューリングマシンによって時間2 cnで決定されないように、絶対定数c > 0が存在するという仮説が立てられています。mは節数を示し、ETHはkSAT時間2o m任意の整数k≥3の場合[26]指数時間仮説は、P≠NPを意味します。

指数時間

Tn )が2 poly(nによって上限が定められている場合、アルゴリズムは指数時間であると言われます。ここで、poly(n )はnの多項式です。より正式には、Tn )がある定数kに対してO(2 n k )によって制限されている場合、アルゴリズムは指数関数的な時間になります。決定論的チューリングマシンで指数時間アルゴリズムを認める問題は、EXPとして知られる複雑さのクラスを形成します。

指数時間は、 Tn)= 2 Onを持つアルゴリズムを指すために使用されることがあります。ここで、指数は最大でnの線形関数ですこれにより、複雑度クラスEが発生します。

階乗時間

T(n)が階乗関数n!によって上限が定められている場合、アルゴリズムは階乗時間であると言われます。階乗時間は指数時間(EXP)のサブセットです。 すべてのためにただし、Eのサブセットではありません。

階乗時間で実行されるアルゴリズムの例は、試行錯誤に基づく悪名高い非効率的なソートアルゴリズムであるbogosortです。Bogosortは、並べ替えが見つかるまでリストを繰り返しシャッフルすることにより、 n個のアイテムのリストを並べ替えます。平均的なケースでは、ボゴソートアルゴリズムを通過するたびに、n!の1つが調べられます。n個のアイテムの注文アイテムが異なる場合、そのような順序は1つだけソートされます。ボゴソートは、無限の猿定理と遺産を共有しています。

二重指数時間

Tn )が2 2 poly(nによって上限が定められている場合、アルゴリズムは二重指数時間であると言われます。ここで、poly(n )はnの多項式です。このようなアルゴリズムは、複雑度クラス2-EXPTIMEに属します。

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

も参照してください

参考文献

  1. ^ a b Sipser、Michael(2006)。計算理論の紹介コーステクノロジー株式会社ISBN 0-619-21764-2
  2. ^ メールホルン、カート; Naher、Stefan(1990)。「 O(両対数N時間とOn空間での有界順序辞書」。情報処理レター35(4):183–189。土井10.1016 / 0020-0190(90)90022-P
  3. ^ タオ、テレンス(2010)。「1.11AKS素数性テスト」部屋のイプシロン、II:数学ブログの3年目のページ数学の大学院研究。117.ロードアイランド州プロビデンス:アメリカ数学会。pp。82–86。土井10.1090 / gsm / 117ISBN 978-0-8218-5280-4MR2780010 _
  4. ^ Lenstra、HW Jr .; ポメランス、カール(2019)。「ガウスの周期による素数性テスト」(PDF)欧州数学学会誌21(4):1229–1269。土井10.4171 / JEMS / 861MR3941463_ S2CID127807021_   
  5. ^ a b Babai、László ; フォートノフ、ランス; ニサン、N。; ウィグダーソン、アヴィ(1993)。「EXPTIMEに公開可能な証明がない限り、BPPには指数以下の時間シミュレーションがあります」。計算の複雑さベルリン、ニューヨーク:Springer-Verlag3(4):307–318。土井10.1007 / BF01275486S2CID14802332_ 
  6. ^ ブラッドフォード、フィリップG。; ローリンズ、グレゴリーJE; シャノン、グレゴリーE.(1998)。「ポリログ時間での効率的な行列連鎖順序付け」。SIAM Journal onComputing27(2):466–490。土井10.1137 / S0097539794270698MR1616556_ 
  7. ^ ホルム、ジェイコブ; ローテンバーグ、エヴァ(2020)。「多対数時間での完全に動的な平面性テスト」。マカリチェフでは、コンスタンティン。マカリチェフ、ユーリー; トゥルシアーニ、マドゥール; カマト、ガウタム; チュゾイ、ジュリア(編)。コンピューティング理論に関する第52回ACMSIGACTシンポジウムの議事録、STOC 2020、米国イリノイ州シカゴ、2020年6月22〜26日コンピューティングマシナリー協会。pp。167–180。arXiv1911.03449土井10.1145 /3357713.3384249
  8. ^ クマール、ラビ; ルビンフェルド、ロニット(2003)。「劣線形時間アルゴリズム」(PDF)SIGACTニュース34(4):57–67。土井10.1145 /954092.954103S2CID65359_  
  9. ^ Naik、Ashish V。; リーガン、ケネスW。; シヴァクマール、D。(1995)。「準線形時間計算量理論について」(PDF)理論計算機科学148(2):325–349。土井10.1016 / 0304-3975(95)00031-QMR1355592_  
  10. ^ セッジウィック、ロバート; ウェイン、ケビン(2011)。アルゴリズム(第4版)。ピアソン教育。p。186。
  11. ^ Papadimitriou、クリストスH.(1994)。計算の複雑さマサチューセッツ州レディング:アディソン-ウェスリー。ISBN 0-201-53082-1
  12. ^ コブハム、アラン(1965)。「関数の本質的な計算の難しさ」。Proc。科学の論理、方法論、および哲学II北ホラント。
  13. ^ グロチェル、マーティン; LászlóLovász ; アレクサンダーシュライバー(1988)。「複雑さ、オラクル、および数値計算」。幾何学的アルゴリズムと組み合わせの最適化スプリンガー。ISBN 0-387-13624-X
  14. ^ Schrijver、Alexander(2003)。「アルゴリズムと複雑さに関する予備知識」。組み合わせ最適化:多面体と効率1.スプリンガー。ISBN 3-540-44389-4
  15. ^ ブレイバーマン、マーク; Kun-Ko、Young; ルビンスタイン、アビアド; ワインスタイン、オムリ(2017)。「完全な完全性を備えた最も密度の高いk-サブグラフのETH硬度」。クラインでは、Philip N.(ed。)離散アルゴリズムに関する第28回ACM-SIAMシンポジウムの議事録、SODA 2017、スペイン、バルセロナ、ホテルポルタフィラ、1月16〜19日工業および応用数学学会。pp。1326–1341。arXiv1504.08352土井10.1137 /1.9781611974782.86MR3627815_ 
  16. ^ 複雑さの動物園クラスQP:準多項式-時間
  17. ^ a b インパリアッツォ、ラッセル; パトゥリ、ラマモハン(2001)。「 k -SATの複雑さについて(PDF)コンピュータとシステム科学のジャーナル62(2):367–375。土井10.1006 /jcss.2000.1727MR1820597_  
  18. ^ アーロンソン、スコット(2009年4月5日)。「かなり指数関数的ではないジレンマ」シュテットル-最適化2009年12月2日取得
  19. ^ 複雑さの動物園クラスSUBEXP:決定論的サブ指数-時間
  20. ^ Moser、P。(2003)。「小さな複雑さのクラスに関するベアのカテゴリー」。AndrzejLingasでは; ベングト・J・ニルソン(編)。計算理論の基礎:第14回国際シンポジウム、FCT 2003、スウェーデン、マルメ、2003年8月12〜15日、議事録コンピュータサイエンスの講義ノート2751.ベルリン、ニューヨーク:Springer-Verlag。pp。333–342。土井10.1007 / 978-3-540-45077-1_31ISBN 978-3-540-40543-6ISSN0302-9743 _
  21. ^ ミルターセン、PB(2001)。「複雑さのクラスのランダム化解除」。ランダム化コンピューティングハンドブック組み合わせ最適化。クルーワーアカデミックパブ。9:843。doi 10.1007 / 978-1-4615-0013-1_19ISBN 978-1-4613-4886-3
  22. ^ Kuperberg、Greg(2005)。「二面体隠れサブグループ問題のための準指数時間量子アルゴリズム」。SIAM Journal onComputingフィラデルフィア。35(1):188。arXivquant-ph / 0302112土井10.1137 / s0097539703436345ISSN1095-7111_ S2CID15965140_  
  23. ^ Oded Regev(2004)。「多項式空間を伴う二面体隠れサブグループ問題のためのサブ指数時間アルゴリズム」。arXivquant-ph / 0406151v1
  24. ^ グロエ、マーティン; ノイエン、ダニエル(2021)。「グラフ同型問題に関する最近の進歩」。arXiv2011.01366 {{cite journal}}引用ジャーナルには|journal=ヘルプ)が必要です
  25. ^ フラム、イェルク; グロエ、マーティン(2006)。パラメータ化された複雑性理論スプリンガー。p。417. ISBN 978-3-540-29952-3
  26. ^ Impagliazzo、R .; パトゥリ、R。; ゼーン、F。(2001)。「どの問題が非常に指数関数的に複雑になっていますか?」コンピュータとシステム科学のジャーナル63(4):512–530。土井10.1006 /jcss.2001.1774
  27. ^ マイヤー、エルンストW .; メイヤー、アルバートR.(1982)。「可換半群と多項式理想の文章題の複雑さ」数学の進歩46(3):305–329。土井10.1016 / 0001-8708(82)90048-2MR0683204_ 
  28. ^ ダベンポート、ジェームズH。; ハインツ、ヨース(1988)。「実際の量化記号消去法は二重指数関数です」Journal of SymbolicComputation5(1–2):29–35。土井10.1016 / S0747-7171(88)80004-XMR0949111_ 
  29. ^ コリンズ、ジョージE.(1975)。「柱形代数分解による実閉体の量化記号消去法」。ブラッケージでは、H。(編)。オートマトン理論と形式言語:第2回GI会議、Kaiserslautern、1975年5月20〜23日コンピュータサイエンスの講義ノート。33.スプリンガー。pp。134–183。土井10.1007 / 3-540-07407-4_17MR0403962_