EITC/IS/CCTF計算複雑性理論の基礎は、インターネットで広く使用されている古典的な非対称公開鍵暗号の基礎でもある、コンピュータサイエンスの基礎の理論的側面に関するヨーロッパのIT認定プログラムです。
EITC/IS/CCTF計算複雑性理論の基礎のカリキュラムは、決定論的および非決定論的有限状態マシン、通常の言語、コンテキストフリーグラマーおよび言語理論、オートマトン理論、チューリングなどの基本概念に基づくコンピューターサイエンスおよび計算モデルの基礎に関する理論的知識をカバーしています。このEITC認定の参照として包括的なビデオ教訓的なコンテンツを含む、次の構造内の基本的なセキュリティアプリケーションのマシン、問題の決定可能性、再帰、論理、およびアルゴリズムの複雑さ。
アルゴリズムの計算の複雑さは、アルゴリズムを操作するために必要なリソースの量です。 時間とメモリのリソースには特別な注意が払われています。 問題の複雑さは、それを解決するための最良のアルゴリズムの複雑さとして定義されます。 アルゴリズムの分析は、明示的に与えられたアルゴリズムの複雑さの研究ですが、計算の複雑さの理論は、最もよく知られているアルゴリズムを使用した問題解決の複雑さの研究です。 アルゴリズムの複雑さは、解決する問題の複雑さに対する上限の制約であるため、両方のドメインが絡み合っています。 さらに、効率的なアルゴリズムを構築する際に、特定のアルゴリズムの複雑さを解決する問題の複雑さと比較することがしばしば必要になります。 ほとんどの場合、問題の難しさに関して入手できる唯一の情報は、それが最も効率的な既知の手法の複雑さよりも少ないということです。 その結果、アルゴリズム分析と複雑性理論の間には多くの重複があります。
複雑性理論は、コンピュータサイエンスの基礎としての計算モデルの基礎だけでなく、現代のネットワーク、特にインターネットで広く普及している古典的な非対称暗号(いわゆる公開鍵暗号)の基礎でも重要です。 公開鍵暗号化は、たとえば、多数を素因数分解するなど、特定の非対称数学問題の計算が難しいことに基づいています(この操作は、解くための効率的な古典的アルゴリズムが知られていないため、複雑性理論の分類では難しい問題です。これは、問題の入力サイズの増加に伴って指数関数的にではなく、多項式的にスケーリングするリソースを使用します。これは、既知の素因数に乗算して元の大きな数を与える非常に単純な逆演算とは対照的です)。 公開鍵暗号のアーキテクチャでこの非対称性を使用する(秘密鍵から簡単に計算できる公開鍵間の計算上非対称な関係を定義することにより、秘密鍵を公開鍵から簡単にコンピューター化することはできませんが、公開することができます)公開鍵をアナウンスし、他の通信側がそれをデータの非対称暗号化に使用できるようにします。これは、結合された秘密鍵でのみ復号化でき、第三者が計算で利用できないため、通信が安全になります)。
計算の複雑さの理論は、主に、第二次世界大戦で勝利した同盟国で大きな役割を果たしたナチスドイツのエニグマ暗号を破るのに重要な仕事をしたアランチューリングなどのコンピューターサイエンスとアルゴリズムのパイオニアの業績に基づいて開発されました。 隠された情報を明らかにするためにデータ(主に暗号化された通信)を分析する計算プロセスを考案および自動化することを目的とした暗号解読は、暗号システムを侵害し、暗号化された通信のコンテンツにアクセスするために使用されました。 また、最初の最新のコンピューター(当初はコードブレイクの戦略的目標に適用された)の開発を触媒した暗号解読でもありました。 英国の巨像(最初の近代的な電子およびプログラムコンピュータと見なされている)の前には、エニグマ暗号の解読を支援するためにマリアンレイェフスキによって設計された電子計算デバイスであるポーランドの「爆弾」があり、ポーランドの諜報機関によって英国に引き渡されました。 1939年にポーランドがドイツに侵略された後、捕獲されたドイツのエニグマ暗号化マシン。このデバイスに基づいて、アランチューリングは、ドイツの暗号化通信をうまく破るためのより高度な対応物を開発しました。
アルゴリズムの実行に必要なリソースの量は入力のサイズによって異なるため、複雑さは通常、関数f(n)として表されます。ここで、nは入力サイズであり、f(n)は最悪の場合の複雑さです(サイズnのすべての入力で必要なリソースの最大量)または平均的な場合の複雑さ(サイズnのすべての入力でのリソースの量の平均)。 サイズnの入力で必要な基本操作の数は、一般に時間計算量として表されます。基本操作は、特定のコンピューターでは一定の時間がかかり、別のコンピューターで実行すると一定の係数でのみ変化すると考えられています。 サイズnの入力でアルゴリズムが必要とするメモリの量は、スペースの複雑さとして知られています。
時間は最も一般的に考えられるリソースです。 「複雑さ」という用語が修飾子なしで使用される場合、それは通常、時間の複雑さを指します。
従来の時間の単位(秒、分など)は、選択したコンピューターとテクノロジーの進歩に依存しすぎているため、複雑さの理論では使用されていません。 たとえば、今日のコンピューターは1960年代のコンピューターよりも大幅に高速にアルゴリズムを実行できますが、これはアルゴリズムの固有の品質ではなく、コンピューターハードウェアの技術的進歩によるものです。 複雑性理論の目標は、アルゴリズムに固有の時間の必要性、またはアルゴリズムが任意のコンピューターに課す基本的な時間制限を定量化することです。 これは、計算中に実行された基本的な操作の数を数えることによって達成されます。 これらの手順は、特定のマシンで一定の時間がかかると見なされるため、一般にステップと呼ばれます(つまり、入力の量に影響されません)。
もうXNUMXつの重要なリソースは、アルゴリズムを実行するために必要なコンピューターメモリの量です。
もうXNUMXつのよく使用されるリソースは、算術演算の量です。 このシナリオでは、「算術の複雑さ」という用語が使用されます。 時間計算量は、一般に、計算中に発生する数値のXNUMX進表現のサイズに対する上限の制約がわかっている場合、一定の係数による算術の複雑さの積です。
計算中に使用される整数のサイズは、多くの方法で制約されておらず、算術演算に一定の時間が必要であると想定するのは非現実的です。 その結果、ビットの複雑さとしても知られる時間の複雑さは、算術の複雑さよりも大幅に高くなる可能性があります。 たとえば、nn整数行列の行列式を計算することの算術的な難しさは、標準的な手法(ガウスの消去法)ではO(n ^ 3)です。 係数のサイズは計算中に指数関数的に拡大する可能性があるため、同じメソッドのビットの複雑さはnで指数関数的になります。 これらの手法をマルチモジュラー演算と組み合わせて使用すると、ビットの複雑さをO(n ^ 4)に減らすことができます。
ビットの複雑さは、正式な用語では、アルゴリズムを実行するために必要なビットに対する操作の数を指します。 これは、ほとんどの計算パラダイムで一定の係数までの時間計算量に等しくなります。 コンピューターに必要なマシンワードの操作数は、ビットの複雑さに比例します。 したがって、現実的な計算モデルの場合、時間計算量とビット複雑度は同じです。
並べ替えや検索でよく考慮されるリソースは、エントリの比較量です。 データが適切に配置されている場合、これは時間計算量の良い指標です。
すべての潜在的な入力で、アルゴリズムのステップ数を数えることは不可能です。 入力の複雑さはそのサイズとともに増加するため、通常、入力のサイズn(ビット単位)の関数として表されます。したがって、複雑さはnの関数です。 ただし、同じサイズの入力の場合、アルゴリズムの複雑さは大幅に異なる可能性があります。 その結果、さまざまな複雑さの関数が日常的に使用されます。
最悪の場合の複雑さは、すべてのサイズnの入力のすべての複雑さの合計ですが、平均の場合の複雑さは、すべてのサイズnの入力のすべての複雑さの合計です(これは、特定のサイズの可能な入力の数が有限の)。 「複雑さ」という用語をさらに定義せずに使用する場合、最悪の場合の時間計算量が考慮されます。
最悪の場合と平均的な場合の複雑さは、正しく計算するのが難しいことで有名です。 さらに、これらの正確な値は、マシンまたは計算パラダイムを変更すると複雑さがわずかに変化するため、実用性はほとんどありません。 さらに、nの値が小さい場合、リソースの使用は重要ではないため、nが小さい場合の複雑さの低さよりも、実装の容易さが魅力的であることがよくあります。
これらの理由から、高いnに対する複雑さの振る舞い、つまりnが無限大に近づくときの漸近的な振る舞いに最も注意が払われます。 その結果、複雑さを示すために大きなO表記が一般的に使用されます。
計算モデル
複雑さを判断するには、時間の単位で実行される重要な操作を指定することで構成される計算モデルの選択が重要です。 これは、計算パラダイムが具体的に説明されていない場合、マルチテープチューリングマシンと呼ばれることがあります。
計算の決定論的モデルは、マシンの後続の状態と実行される操作が完全に前の状態によって定義されるモデルです。 再帰関数、ラムダ計算、およびチューリングマシンが最初の決定論的モデルでした。 ランダムアクセスマシン(RAMマシンとも呼ばれます)は、実際のコンピューターをシミュレートするための一般的なパラダイムです。
計算モデルが定義されていない場合、通常はマルチテープチューリングマシンが想定されます。 マルチテープチューリングマシンでは、時間計算量はほとんどのアルゴリズムのRAMマシンと同じですが、この同等性を実現するには、データをメモリに格納する方法にかなりの注意が必要になる場合があります。
非決定性チューリングマシンなどの非決定性コンピューティングモデルでは、計算のいくつかのステップでさまざまな選択を行うことができます。 複雑さの理論では、実行可能なすべてのオプションが同時に考慮され、非決定論的な時間計算量は、常に最良の選択が行われるときに必要な時間です。 言い換えると、計算は必要な数の(同一の)プロセッサで同時に実行され、非決定論的計算時間は、最初のプロセッサが計算を完了するのにかかる時間です。 この並列処理は、たとえばShorの小さな整数の因数分解など、特殊な量子アルゴリズムを実行するときに、重ね合わされたエンタングル状態を使用することにより、量子コンピューティングで使用できます。
このような計算モデルは現在実用的ではありませんが、特に「多項式時間」と「非決定論的多項式時間」を使用して生成された複雑度クラスが少なくとも上位であるかどうかを尋ねるP = NP問題に関して理論的に重要です。境界は同じです。 決定論的コンピューターでは、NPアルゴリズムのシミュレーションには「指数関数的な時間」が必要です。 非決定論的システムでタスクを多項式時間で解くことができる場合、そのタスクはNP難易度クラスに属します。 問題がNPにあり、他のNP問題よりも簡単ではない場合、それはNP完全であると言われます。 ナップサック問題、巡回セールスマン問題、およびブール充足可能性問題はすべて、NP完全な組み合わせ問題です。 最もよく知られているアルゴリズムは、これらすべての問題に対して指数関数的な複雑さを持っています。 これらの問題のいずれかが決定性マシンで多項式時間で解決できれば、すべてのNP問題も多項式時間で解決でき、P = NPが確立されます。 2017年の時点で、P NPは、NP問題の最悪の状況を解決するのが根本的に困難である、つまり、興味深い入力長が与えられた実行可能な期間(数十年)よりもはるかに長い時間がかかることを意味すると広く考えられています。
並列分散コンピューティング
並列分散コンピューティングでは、すべてが同時に動作する複数のプロセッサ間で処理を分割します。 さまざまなモデルの基本的な違いは、プロセッサ間でデータを送信する方法です。 並列コンピューティングでは通常、プロセッサ間のデータ転送は非常に高速ですが、分散コンピューティングではプロセッサ間のデータ転送はネットワークを介して行われるため、大幅に遅くなります。
N個のプロセッサでの計算には、少なくともXNUMX個のプロセッサでかかる時間のNの商が必要です。 実際には、一部のサブタスクは並列化できず、一部のプロセッサは別のプロセッサからの結果を待つ必要がある場合があるため、この理論的に理想的な限界は達成されません。
したがって、重要な複雑さの問題は、プロセッサの数による計算時間の積が、単一のプロセッサで同じ計算を実行するために必要な時間に可能な限り近くなるようにアルゴリズムを開発することです。
量子計算
量子コンピューターは、量子力学に基づく計算モデルを備えたコンピューターです。 チャーチチューリングの理論は量子コンピューターにも当てはまり、量子コンピューターが解決できる問題はすべてチューリングマシンでも解決できることを意味します。 ただし、一部のタスクは、時間計算量が大幅に低い従来のコンピューターではなく、量子コンピューターを使用して理論的に解決される場合があります。 実用的な量子コンピューターを開発する方法を誰も知らないので、当分の間、これは厳密に理論的です。
量子複雑性理論は、量子コンピューターで解決できるさまざまな種類の問題を調査するために作成されました。 これは、量子コンピューターの攻撃に耐性のある暗号化プロトコルを作成するプロセスであるポスト量子暗号化で利用されます。
問題の複雑さ(下限)
未発見の手法を含め、問題を解決する可能性のあるアルゴリズムの複雑さの最小値は、問題の複雑さです。 結果として、問題の複雑さは、それを解決するアルゴリズムの複雑さと同じになります。
結果として、大きなO表記で与えられる複雑さは、アルゴリズムとそれに伴う問題の両方の複雑さを表します。
一方、問題の複雑さに関する自明でない下限を取得することはしばしば困難であり、そうするための戦略はほとんどありません。
ほとんどの問題を解決するには、すべての入力データを読み取る必要があります。これには、データの大きさに比例した時間がかかります。 結果として、そのような問題は、少なくとも線形の複雑さ、または大きなオメガ表記では、Ω(n)の複雑さを持ちます。
数式処理や計算代数幾何学の問題など、いくつかの問題には非常に大きな解決策があります。 出力を書き込む必要があるため、複雑さは出力の最大サイズによって制約されます。
ソートアルゴリズムに必要な比較の数には、Ω(nlogn)の非線形下限があります。 結果として、その複雑さはO(nlogn)であるため、最良のソートアルゴリズムが最も効率的です。 nがあるという事実! n個の物を整理する方法は、この下限につながります。 それぞれの比較がこのnのコレクションを分割するからです! 注文を2つに分割する場合、すべての注文を区別するために必要なN回の比較の数はXNUMXN> n!である必要があります。これは、スターリングの式によるO(nlogn)を意味します。
問題を別の問題に減らすことは、複雑さの制約を減らすための一般的な戦略です。
アルゴリズム開発
アルゴリズムの複雑さを評価することは、期待されるパフォーマンスに関する有用な情報を提供するため、設計プロセスの重要な要素です。
現代のコンピューター能力の指数関数的成長を予測するムーアの法則の結果として、アルゴリズムの複雑さを評価することの関連性が低くなるというのは、よくある誤解です。 電力の増加により大量のデータ(ビッグデータ)の処理が可能になるため、これは正しくありません。 たとえば、本の参考文献など、数百のエントリのリストをアルファベット順に並べ替える場合、どのアルゴリズムも2秒未満でうまく機能するはずです。 一方、10万のエントリ(たとえば、大都市の電話番号)の場合、O(n30,000,000)の比較を必要とする基本的なアルゴリズムでは、1,000,000兆の比較を実行する必要があり、3の速度で10時間かかります。 XNUMX秒あたりXNUMX万回の比較。 一方、クイックソートとマージソートでは、nlognの比較のみが必要です(前者の場合は平均的な場合の複雑さ、後者の場合は最悪の場合の複雑さとして)。 これにより、n = XNUMXの場合に約XNUMXの比較が生成されます。これは、XNUMX秒あたりXNUMX万の比較でわずかXNUMX秒かかります。
結果として、複雑さを評価することで、実装前に多くの非効率的なアルゴリズムを排除できる可能性があります。 これは、考えられるすべてのバリアントをテストすることなく、複雑なアルゴリズムを微調整するためにも使用できます。 複雑さの研究により、複雑なアルゴリズムの最もコストのかかるステップを決定することにより、実装の効率を高めるための努力に集中することができます。
認定カリキュラムについて詳しく知るために、以下の表を展開して分析することができます。
EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum は、ビデオ形式でオープンアクセスの教材を参照しています。 学習プロセスは、関連するカリキュラム部分をカバーする段階的な構造 (プログラム -> レッスン -> トピック) に分かれています。 ドメインの専門家による無制限のコンサルティングも提供されます。
認定手続きの確認について詳しくは 仕組み.
主な支援カリキュラムの読み物
S. Arora、B。Barak、計算の複雑さ:現代的なアプローチ
https://theory.cs.princeton.edu/complexity/book.pdf
二次支援カリキュラムの読み物
O.ゴールドライヒ、複雑性理論の紹介:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
離散数学に関する支援カリキュラムの読み物
J. Aspnes、離散数学に関する注記:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
グラフ理論に関する支援カリキュラムの読み物
R.ディーステル、グラフ理論:
https://diestel-graph-theory.com/
EITC/IS/CCTF 計算複雑性理論の基礎プログラムの完全なオフライン自己学習準備資料を PDF ファイルでダウンロードします。