Loading article…
理論計算機科学および数学において、計算複雑性理論は、計算問題をそのリソース使用量に基づいて分類し、これらの分類間の関係を探求することに焦点を当てています。計算問題とは、コンピュータによって解決されるタスクであり、アルゴリズムなどの数学的手順を機械的に適用することによって解決できます。
どのようなアルゴリズムを用いるかにかかわらず、解決に多大なリソースを必要とする問題は、本質的に難しい問題とみなされる。この理論は、こうした問題を研究するための計算の数学的モデルを導入し、計算の複雑さ、すなわち、時間や記憶容量といった解決に必要なリソースの量を定量化することで、この直感を形式化する。
複雑性の他の尺度も使用されており、例えば、通信量（通信複雑性で使用）、回路内のゲート数（回路複雑性で使用）、プロセッサ数（並列コンピューティングで使用）などがあります。計算複雑性理論の役割の1つは、コンピュータができることとできないことの実際的な限界を決定することです。7つのミレニアム賞問題の1つであるP対NP問題[ 1 ]は、計算複雑性の分野の一部です。
理論計算機科学において密接に関連する分野として、アルゴリズム解析と計算可能性理論がある。アルゴリズム解析と計算複雑性理論の重要な違いは、前者が特定のアルゴリズムが問題を解決するために必要なリソース量を分析することに重点を置いているのに対し、後者は同じ問題を解決するために使用できる可能性のあるすべてのアルゴリズムについてより一般的な問いを立てる点にある。より正確に言えば、計算複雑性理論は、適切な制限されたリソースで解決できる問題とできない問題を分類しようとする。逆に、利用可能なリソースに制限を設けることが、計算複雑性と計算可能性理論を区別する点である。後者の理論は、原理的にどのような種類の問題がアルゴリズム的に解決できるのかを問うている。
計算問題は、無限に続くインスタンスの集合と、各インスタンスに対する（空集合の場合もある）解の集合として捉えることができます。計算問題への入力文字列は問題インスタンスと呼ばれ、問題そのものと混同してはなりません。計算複雑性理論では、問題とは解決すべき抽象的な問いを指します。これに対し、この問題のインスタンスは、決定問題への入力として使用できる、より具体的な発話です。例えば、素数判定問題を考えてみましょう。インスタンスは数値（例：15）であり、解は、その数値が素数であれば「はい」、そうでなければ「いいえ」です（この場合、15は素数ではないため、答えは「いいえ」です）。言い換えれば、インスタンスは問題への特定の入力であり、解は与えられた入力に対応する出力です。
問題とインスタンスの違いをさらに明確にするために、巡回セールスマン問題の決定版の次のインスタンスを考えてみましょう。ドイツの14の大都市すべてを通過する、最大2000キロメートルのルートは存在するでしょうか？この特定のインスタンスに対する定量的な答えは、ミラノの14か所を巡る、全長が最大10キロメートルの往復ルートを求めるなど、他のインスタンスを解決するのにはほとんど役に立ちません。このため、計算複雑性理論は、特定のインスタンスではなく、計算上の問題を扱います。
計算上の問題を考える場合、問題インスタンスはアルファベット上の文字列です。通常、アルファベットはバイナリアルファベット（つまり、{0,1}の集合）とみなされ、したがって文字列はビット列になります。実際のコンピュータと同様に、ビット列以外の数学的オブジェクトは適切にエンコードする必要があります。たとえば、整数はバイナリ表記で表現でき、グラフは隣接行列を介して直接エンコードするか、隣接リストをバイナリでエンコードすることでエンコードできます。
計算複雑性理論の定理の証明の中には、入力エンコーディングの具体的な選択を前提とするものもあるが、議論はエンコーディングの具体的な選択に依存しないように、十分に抽象的に保つよう努めるべきである。これは、異なる表現形式を効率的に相互変換できることを保証することによって実現できる。
決定問題は、計算複雑性理論における中心的な研究対象の一つです。決定問題とは、答えが「はい」か「いいえ」（あるいは「1」か「0」）のいずれかである計算問題の一種です。決定問題は形式言語として捉えることができ、その言語の要素は出力が「はい」となるインスタンスであり、要素でないインスタンスは出力が「いいえ」となるインスタンスです。目的は、アルゴリズムを用いて、与えられた入力文字列が対象となる形式言語の要素であるかどうかを判定することです。この問題を判定するアルゴリズムが「はい」という答えを返す場合、そのアルゴリズムは入力文字列を受け入れると言われ、そうでない場合は入力を拒否すると言われます。
決定問題の一例として、次のようなものがあります。入力は任意のグラフです。この問題は、与えられたグラフが連結グラフであるかどうかを判定することです。この決定問題に関連付けられる形式言語は、すべての連結グラフの集合です。この言語を正確に定義するには、グラフをバイナリ文字列としてどのようにエンコードするかを決定する必要があります。
関数問題とは、入力ごとに単一の出力（全体関数の出力）が期待される計算問題ですが、その出力は決定問題よりも複雑になる場合があります。つまり、出力は単に「はい」か「いいえ」だけではありません。代表的な例としては、巡回セールスマン問題や整数因数分解問題などがあります。
関数問題の概念は決定問題の概念よりもはるかに豊かであると考えるのは魅力的である。しかし、関数問題は決定問題として再定式化できるため、実際にはそうではない。たとえば、2 つの整数の乗算は、3 つの組の集合として表現できる。関係が成り立つ。与えられた3つの数がこの集合の要素であるかどうかを判断することは、2つの数を掛け合わせる問題を解くことに相当する。
計算問題の難易度を測るには、最良のアルゴリズムが問題を解決するのにどれくらいの時間を要するかを調べればよい。しかし、実行時間は一般的にインスタンスに依存する。特に、インスタンスが大きいほど解決に時間がかかる。したがって、問題を解決するのに必要な時間（または必要な空間、あるいは複雑さの尺度）は、インスタンスのサイズの関数として計算される。入力サイズは通常ビット単位で測定される。複雑性理論は、入力サイズが増加するにつれてアルゴリズムがどのようにスケーリングするかを研究する。例えば、グラフが連結かどうかを判定する問題において、グラフのサイズが大きくなると、問題の解決にどれだけの時間がかかるか。頂点数と、グラフの所要時間を比較すると、頂点？
入力サイズが所要時間は、同じサイズの異なる入力にかかる時間は異なる可能性があるため、最悪の場合の時間計算量はは、サイズ のすべての入力にかかる最大時間として定義されます。。 もしは多項式であるならば、そのアルゴリズムは多項式時間アルゴリズムであると言われる。コブハムの論文は、問題が実行可能な量のリソースで解決できるのは、その問題が多項式時間アルゴリズムを許容する場合に限ると主張している。
チューリングマシンは、汎用計算機の数学モデルです。これは、テープに記録された記号を操作する理論的な装置です。チューリングマシンは、実用的な計算技術としてではなく、高度なスーパーコンピュータから鉛筆と紙を使う数学者まで、あらゆる計算機の汎用モデルとして設計されています。アルゴリズムで解決できる問題があれば、その問題を解決するチューリングマシンが存在すると考えられています。実際、これはチャーチ＝チューリングのテーゼの主張です。さらに、 RAMマシン、コンウェイのライフゲーム、セルオートマトン、ラムダ計算、あらゆるプログラミング言語など、今日知られている他の計算モデルで計算できるものはすべて、チューリングマシンでも計算できることが知られています。チューリングマシンは数学的に分析しやすく、他のどの計算モデルにも劣らないほど強力であると考えられているため、計算複雑性理論において最も一般的に使用されるモデルとなっています。
複雑性クラスを定義するために、決定性チューリングマシン、確率性チューリングマシン、非決定性チューリングマシン、量子チューリングマシン、対称チューリングマシン、交代チューリングマシンなど、多くの種類のチューリングマシンが用いられます。原理的にはすべて同等の能力を持っていますが、時間や空間などのリソースが限られている場合、これらのうちいくつかは他のものよりも強力になる可能性があります。
決定性チューリングマシンは、最も基本的なチューリングマシンであり、固定された一連のルールを使用して将来の動作を決定します。確率的チューリングマシンは、ランダムビットを追加した決定性チューリングマシンです。確率的な決定を行う能力は、アルゴリズムが問題をより効率的に解決するのに役立つことがよくあります。ランダムビットを使用するアルゴリズムは、ランダム化アルゴリズムと呼ばれます。非決定性チューリングマシンは、非決定性という追加機能を持つ決定性チューリングマシンであり、チューリングマシンは、与えられた状態から複数の可能な将来の動作を持つことができます。非決定性を理解する1つの方法は、チューリングマシンが各ステップで多くの可能な計算パスに分岐し、これらの分岐のいずれかで問題を解決した場合、問題を解決したと言われるというものです。明らかに、このモデルは物理的に実現可能なモデルを意図したものではなく、特に興味深い複雑性クラスを生み出す理論的に興味深い抽象マシンにすぎません。例については、非決定性アルゴリズムを参照してください。
文献では、標準的なマルチテープチューリングマシンとは異なる多くのマシンモデルが提案されている。例えば、ランダムアクセスマシンなどである。驚くべきことに、これらのモデルはそれぞれ、追加の計算能力を提供することなく、別のモデルに変換することができる。これらの代替モデルの時間とメモリの消費量は異なる場合がある。[ 2 ]これらのモデルすべてに共通しているのは、マシンが決定論的に動作することである。
しかし、計算上の問題の中には、より特殊なリソースの観点から分析しやすいものもあります。例えば、非決定性チューリングマシンは、一度に多くの異なる可能性を検証するために分岐を許容する計算モデルです。非決定性チューリングマシンは、アルゴリズムを物理的に計算する方法とはほとんど関係がありませんが、その分岐は、分析したい多くの数学モデルを正確に捉えているため、非決定性時間は計算上の問題を分析する上で非常に重要なリソースとなります。
与えられた時間と空間を使って問題を解決するとはどういうことかを正確に定義するために、決定論的チューリングマシンなどの計算モデルが用いられる。決定論的チューリングマシンが要求する時間は入力時これは、機械が停止して答え（「はい」または「いいえ」）を出力するまでに行う状態遷移、つまりステップの総数です。チューリングマシン時間内に動作すると言われている必要な時間長さの各入力に対して最大で意思決定問題時間内に解決できる時間内に動作するチューリングマシンが存在する場合それで問題が解決する。複雑性理論は問題をその難易度に基づいて分類することに関心があるため、何らかの基準に基づいて問題の集合を定義する。例えば、時間内に解決可能な問題の集合決定性チューリングマシン上では、DTIMEで表されます()
空間要件についても同様の定義が可能である。時間と空間は最もよく知られた複雑性リソースであるが、あらゆる複雑性尺度は計算リソースとみなすことができる。複雑性尺度は、一般的にはBlumの複雑性公理によって定義される。複雑性理論で使用されるその他の複雑性尺度には、通信複雑性、回路複雑性、決定木複雑性などがある。
最良ケース、最悪ケース、平均ケースの複雑性は、同じサイズの異なる入力の時間複雑性（またはその他の複雑性尺度）を測定する3つの異なる方法を指します。他の問題よりも解決が速い場合もあるため、以下の複雑度を定義します。
安い順から高い順に並べると、最良、平均（離散一様分布）、償却、最悪となります。
例えば、決定論的ソートアルゴリズムであるクイックソートは、整数のリストをソートする問題を扱います。最悪のケースは、ピボットが常にリスト内の最大値または最小値である場合です（つまり、リストは決して分割されません）。この場合、アルゴリズムはO () 入力リストのすべての可能な順列が等確率であると仮定すると、ソートにかかる平均時間は最良のケースは、各ピボット操作でリストが半分に分割され、さらに時間。
計算時間（またはスペース消費量などの類似のリソース）を分類するには、最も効率的なアルゴリズムが特定の問題を解決するのに必要な最大時間の上限と下限を示すことが役立ちます。アルゴリズムの複雑さは、特に指定がない限り、通常は最悪の場合の複雑さとして扱われます。特定のアルゴリズムの分析は、アルゴリズム分析の分野に属します。上限を示すには問題の時間計算量については、実行時間が最大で特定のアルゴリズムが存在することを示すだけでよい。しかし、下限を証明することははるかに困難です。なぜなら、下限は与えられた問題を解決するすべての可能なアルゴリズムについて述べるからです。「すべての可能なアルゴリズム」というフレーズには、今日知られているアルゴリズムだけでなく、将来発見される可能性のあるアルゴリズムも含まれます。下限を示すには、問題では、どのアルゴリズムも時間計算量が以下にならないことを示す必要がある。。
上限と下限は通常、定数係数や小さな項を隠すビッグオー記法を用いて表されます。これにより、境界は使用される計算モデルの具体的な詳細に依存しなくなります。たとえば、ビッグオー記法では次のように書く。
複雑性クラスとは、関連する複雑性を持つ問題の集合のことである。より単純な複雑性クラスは、以下の要素によって定義される。
複雑性クラスの中には、このフレームワークに当てはまらない複雑な定義を持つものがあります。例えば、典型的な複雑性クラスの定義は次のようになります。
しかし、上記の計算時間を具体的な関数で制限すると多くの場合、選択されたマシンモデルに依存する複雑性クラスが生成されます。たとえば、言語マルチテープチューリングマシンでは線形時間で解けるが、シングルテープチューリングマシンのモデルでは必然的に二次時間が必要となる。実行時間に多項式的な変動を許容すれば、コブハム・エドモンズのテーゼによれば、「妥当で一般的な2つの計算モデルにおける時間複雑性は多項式的に関連する」（Goldreich 2008 、第1.2章） 。これが複雑性クラスPの基礎を形成し、これは決定論的チューリングマシンで多項式時間内に解ける決定問題の集合である。対応する関数問題の集合はFPである。
アルゴリズムが使用する時間または空間を制限することで、多くの重要な複雑性クラスを定義できます。このように定義される決定問題の重要な複雑性クラスには、次のようなものがあります。
対数空間クラスは、問題を表現するために必要な空間を考慮していない。
サビッチの定理により、PSPACE = NPSPACE および EXPSPACE = NEXPSPACE であることがわかります。
その他の重要な複雑性クラスには、確率的チューリングマシンを使用して定義されるBPP、ZPP、RP、ブール回路を使用して定義されるACおよびNC 、量子チューリングマシンを使用して定義されるBQPおよびQMAがあります。 #Pは、計数問題 (決定問題ではない) の重要な複雑性クラスです。IPやAMのようなクラスは、対話型証明システムを使用して定義されます。ALLは、すべての決定問題のクラスです。
このように定義された複雑性クラスについては、（例えば）計算時間に関する要件を緩和すると、より大きな問題セットが定義されることを証明したい。特に、DTIME() は DTIME( に含まれています）包含関係が厳密かどうかを知ることは興味深いでしょう。時間と空間の要件については、このような疑問に対する答えは、それぞれ時間と空間の階層定理によって与えられます。これらは、それぞれのリソースを制約することによって定義されるクラスに適切な階層を誘導するため、階層定理と呼ばれています。したがって、一方が他方に適切に含まれるような複雑性クラスのペアが存在します。このような適切な集合包含関係を導出することで、解決できる問題の数を増やすために、どれだけ多くの追加の時間または空間が必要になるかについて定量的な記述を行うことができます。
より正確には、時間階層定理は次のように述べている。 。
空間階層定理は次のように述べている。 。
時間階層定理と空間階層定理は、複雑性クラスの分離結果のほとんどの基礎となっている。例えば、時間階層定理によれば、PはEXPTIMEに厳密に含まれ、空間階層定理によれば、LはPSPACEに厳密に含まれる。
多くの複雑性クラスは、還元という概念を用いて定義されます。還元とは、ある問題を別の問題に変換することです。これは、ある問題が別の問題と同程度の難しさであるという非公式な概念を捉えています。例えば、問題がアルゴリズムを使用して解決できます、より難しくはないそして私たちはこう言いますに縮小削減方法に基づいて、クック削減、カープ削減、レヴィン削減などのさまざまなタイプの削減と、多項式時間削減や対数空間削減などの削減の複雑さの上限に基づくさまざまな削減があります。
最も一般的に用いられる還元法は、多項式時間還元法です。これは、還元処理に多項式時間を要することを意味します。例えば、整数の二乗問題は、2つの整数の乗算問題に還元できます。つまり、2つの整数を乗算するアルゴリズムを、整数の二乗に利用できるということです。実際、乗算アルゴリズムの両方の入力に同じ入力を与えることで、これを実現できます。このように、二乗は乗算に還元できるため、二乗は乗算よりも難しい問題ではないことがわかります。
これは、問題が複雑性クラスにとって難しいという概念を動機づける。問題の種類にとって難しいすべての問題がに還元できるしたがって、より難しいアルゴリズムはあらゆる問題を解決できます難しい問題の概念は、使用される還元法の種類によって異なります。P より大きい複雑性クラスでは、多項式時間還元法が一般的に使用されます。特に、NP に対して難しい問題の集合は、NP 困難問題の集合です。
問題が発生した場合はそして難しい、 それから完成していると言われているこれはつまりは最も難しい問題です（多くの問題が同様に難しい可能性があるので、次のように言うこともできる。は、。）したがって、 NP完全問題のクラスには、NPの中で最も難しい問題が含まれています。つまり、Pに含まれない可能性が最も高い問題です。問題P = NPは解決されていないため、既知のNP完全問題を還元することができ、別の問題に移ります。これは、既知の多項式時間解が存在しないことを示しています。これは、多項式時間解が得られる同様に、すべての NP 問題は集合に還元できるため、多項式時間で解けるNP 完全問題が見つかれば、P = NP となります。 [ 3 ]
複雑性クラス P は、効率的なアルゴリズムが存在する計算タスクをモデル化した数学的抽象化として捉えられることが多い。この仮説はコブハム・エドモンズ説と呼ばれる。一方、複雑性クラスNPには、効率的に解決したい問題が多数含まれているが、ブール充足可能性問題、ハミルトン経路問題、頂点被覆問題など、効率的なアルゴリズムは知られていない。決定性チューリングマシンは特殊な非決定性チューリングマシンであるため、P に含まれる各問題がクラス NP にも属することは容易にわかる。
P と NP が等しいかどうかという問題は、その解決がもたらす広範な影響のため、理論計算機科学における最も重要な未解決問題の 1 つです。[ 3 ]答えがイエスであれば、多くの重要な問題に対してより効率的な解法が存在することが示されます。これには、オペレーションズ リサーチにおけるさまざまなタイプの整数計画問題、ロジスティクスにおける多くの問題、生物学におけるタンパク質構造予測、[ 5 ]および純粋数学の定理の形式的証明を見つける能力が含まれます。[ 6 ] P 対 NP 問題は、クレイ数学研究所が提案したミレニアム賞問題の 1 つです。この問題を解決すると、100 万米ドルの賞金が授与されます。[ 7 ]
ラドナーは、もしすると、次のような問題が生じます。どちらにも属さないまたは-完全。[ 4 ]このような問題はNP中間問題と呼ばれます。グラフ同型問題、離散対数問題、整数因数分解問題は、 NP中間問題と考えられている問題の例です。これらは、NP問題として知られていないごく少数のNP問題です。または-完了。
グラフ同型性問題は、2つの有限グラフが同型であるかどうかを判定する計算問題である。計算複雑性理論における重要な未解決問題は、グラフ同型性問題が、NP完全、またはNP中間。答えは不明だが、少なくともNP完全ではないと考えられている。[ 8 ]グラフ同型性がNP完全であれば、多項式時間階層は第2レベルに縮退する。[ 9 ]多項式階層は有限レベルに縮退しないと広く信じられているため、グラフ同型性はNP完全ではないと考えられている。この問題に対する最良のアルゴリズムは、 László BabaiとEugene Luksによって開発され、実行時間はグラフの場合頂点については、Babai による最近の研究がこの点に関していくつかの新しい視点を提供している可能性がある。[ 10 ]
整数因数分解問題とは、与えられた整数の素因数分解を求める計算問題である。決定問題として表現すると、入力された整数が 1 未満の素因数を持つかどうかを判定する問題である。効率的な整数因数分解アルゴリズムは知られておらず、この事実はRSAアルゴリズムなどのいくつかの現代的な暗号システムの基礎となっている。整数因数分解問題はそして（UPとco-UPでも[ 11 ]）。問題が-完全、多項式時間階層は最初のレベルに縮退します（つまり、等しくなります）整数因数分解の最もよく知られたアルゴリズムは、一般的な数体篩法であり、これは に 時間がかかります。[ 12 ]奇数を因数分解するしかし、この問題に対する最もよく知られた量子アルゴリズムであるショアのアルゴリズムは、多項式時間で実行されます。残念ながら、この事実は、非量子的な計算複雑性クラスに関して、この問題がどこにあるのかを多く語るものではありません。
既知の複雑性クラスの多くは不均等であると疑われているが、これは証明されていない。例えばしかし、。 もし等しくない、 それから等しくないどちらでも。そして、 のような、、、、、など、これらの複雑性クラスはすべて一つのクラスに集約される可能性がある。これらのクラスのいずれかが等しくないことを証明できれば、複雑性理論における大きなブレークスルーとなるだろう。
同様に、補問題（つまり、はい／いいえの答えが逆になっている問題）を含むクラスは、問題。[ 13 ]等しくないしかし、それはまだ証明されていません。これら2つの複雑性クラスが等しくない場合、等しくない、 以来したがって、私たちはそこから。
同様に、（対数空間で解けるすべての問題の集合）は厳密に以下に含まれる。または同等繰り返しますが、この2つの間には多くの複雑性クラスが存在します。そしてまた、それらが異なるクラスなのか、それとも同等のクラスなのかは不明である。
疑われているのはそして等しい。ただし、現在開いている場合は。
理論的には解決できるが、解決するには非現実的に膨大な、ほぼ無限のリソース（例えば時間）を必要とする問題は、解決困難な問題。 [ 14 ]逆に、実際に解決できる問題は、扱いやすい問題とは、文字通り「処理できる問題」のことである。実行不可能な（文字通り「できない」）という扱いにくい問題、 [ 15 ]これは数学的最適化における実行可能な解。 [ 16 ]
扱いやすい問題は、多項式時間で解ける問題とよく関連付けられます（、これはコブハム・エドモンズのテーゼとして知られています。この意味で解決困難な問題として知られているものには、EXPTIME困難な問題が含まれます。は、そうだとすると、NP困難問題もこの意味では解決不可能である。
しかし、この識別は不正確です。次数が大きい、または先頭係数が大きい多項式時間解は急速に増加するため、実用規模の問題には不向きな場合があります。逆に、ゆっくりと増加する指数時間解は、現実的な入力に対して実用的である可能性があり、最悪の場合には時間がかかる解でも、ほとんどの場合または平均的な場合には短時間で済むため、依然として実用的である可能性があります。問題が ではないと言うことは、これは、問題の大きなケースすべてが困難である、あるいはそのほとんどが困難であることを意味するものではありません。例えば、プレスバーガー算術における決定問題は、しかし、ほとんどの場合、妥当な時間で問題を解決するアルゴリズムが既に開発されています。同様に、アルゴリズムはNP完全問題であるナップサック問題を幅広いサイズで2乗時間未満で解決でき、SATソルバーはNP完全問題であるブール充足可能性問題の大規模なインスタンスを日常的に処理しています。
指数時間アルゴリズムが実際には一般的に使用できない理由を理解するために、次のようなプログラムを考えてみましょう。停止する前に操作を行います。小規模な例えば100とすると、コンピュータが毎秒演算を行うと、プログラムは約数年、これは宇宙の年齢と同じ桁数です。はるかに高速なコンピュータを使用しても、このプログラムは非常に小さなインスタンスにしか役立たず、その意味では問題の難しさは技術の進歩とはある程度無関係です。しかし、指数時間アルゴリズムは、運用は実用的になるまで比較的大きくなる。
同様に、多項式時間アルゴリズムが常に実用的であるとは限りません。例えば、実行時間が効率的だと考えるのは不合理であり、小規模な場合を除いては依然として役に立たない。実際、実用上はまたはアルゴリズムは、現実的な規模の問題に対してはしばしば非実用的である。
連続複雑性理論は、数値解析で研究されているように、離散化によって近似される連続関数を含む問題の複雑性理論を指すことができる。数値解析の複雑性理論へのアプローチの1つは、情報に基づく複雑性である[ 17 ]。
連続複雑性理論は、連続動的システムと微分方程式を使用するアナログ計算の使用に関する複雑性理論を指すこともあります。[ 18 ]制御理論は計算の一形態とみなすことができ、微分方程式は連続時間システムおよびハイブリッド離散連続時間システムのモデリングに使用されます。[ 19 ]
アルゴリズムの複雑性解析の初期の例としては、1844年にガブリエル・ラメが行ったユークリッドの互除法の実行時間解析が挙げられる。
アルゴリズム問題の複雑性に特化した本格的な研究が始まる以前に、様々な研究者によって数多くの基礎が築かれていた。中でも最も影響力があったのは、 1936年にアラン・チューリングが定義したチューリングマシンであり、これはコンピュータの非常に堅牢で柔軟な簡略化であることが判明した。
計算複雑性に関する体系的な研究の始まりは、1965 年にJuris HartmanisとRichard E. Stearnsが発表した画期的な論文「アルゴリズムの計算複雑性について」に遡るとされています。この論文では、時間複雑性と空間複雑性の定義が示され、階層定理が証明されました。[ 20 ]さらに、1965 年にEdmonds は、「良い」アルゴリズムとは、実行時間が入力サイズの多項式で制限されるアルゴリズムであると考えることを提案しました。[ 21 ]
特定の制限されたリソースを持つチューリングマシンで解決可能な問題を研究した初期の論文には、ジョン・マイヒルの線形制限オートマトンの定義（マイヒル 1960）、レイモンド・スミュリアンの初等集合の研究（1961）、および山田久雄のリアルタイム計算に関する論文（1962）[ 22 ]などがある。それより少し前には、ソ連出身でこの分野の先駆者であるボリス・トラフテンブロート（1956）が、別の特定の複雑性尺度を研究した。[ 23 ]彼が回想するところによれば、
しかし、オートマトン理論に対する私の当初の関心は、次第に計算複雑性へと移っていきました。これは、スイッチング理論から受け継がれた組み合わせ的手法とアルゴリズム理論の概念的武器庫との刺激的な融合です。これらのアイデアは、1955年に私が「シグナリング関数」という用語を造語した時に思いついたもので、これは今日では一般的に「複雑性尺度」として知られています。[ 24 ]
1967年、マヌエル・ブルムは、計算可能な関数の集合上の複雑性尺度の望ましい性質を規定する一連の公理（現在ではブルム公理として知られている）を定式化し、いわゆるスピードアップ定理という重要な結果を証明した。この分野は、1971年にスティーブン・クックとレオニード・レヴィンがNP完全である実用的な問題の存在を証明したことで発展し始めた。1972年、リチャード・カープは、画期的な論文「組み合わせ問題間の還元可能性」でこの考えを飛躍的に発展させ、計算困難で悪名高い21の多様な組み合わせ問題とグラフ理論問題がNP完全であることを示した。 [ 25 ]
![{\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d50912fbf223d0bbadd2a028262414397fbee1a9)
