平均的なケースの複雑さ

計算複雑性理論では、アルゴリズムの平均複雑度は、アルゴリズムが使用する計算リソース (通常は時間) の量であり、すべての可能な入力にわたって平均化されます。これは、すべての可能な入力に対するアルゴリズムの最大複雑度を考慮した最悪ケースの複雑度と頻繁に対比されます。

平均ケースの複雑性を研究する主な動機は 3 つあります。^[1]まず、最悪のケースでは一部の問題が解決不可能になる場合もありますが、この動作を引き起こす入力は実際にはめったに発生しない可能性があるため、平均ケースの複雑性の方がアルゴリズムのパフォーマンスを測るより正確な指標となる可能性があります。次に、平均ケースの複雑性分析は、暗号化やデランダム化などの分野で利用できる問題の難しい例を生成するツールと手法を提供します。最後に、平均ケースの複雑性により、最良のケースの複雑性が同等のアルゴリズム (たとえばクイックソート) の中から実際に最も効率的なアルゴリズムを区別することができます。

平均ケース分析では、アルゴリズムへの「平均」入力の概念が必要となり、入力に対する確率分布を考案するという問題が生じる。代わりに、ランダム化アルゴリズムを使用することもできる。このようなアルゴリズムの分析は、期待される複雑性という関連する概念につながる。^[2]^{: 28}

歴史と背景

アルゴリズムの平均ケースのパフォーマンスは、1950 年代に計算効率の現代的な概念が開発されて以来研究されてきました。この初期の研究の多くは、最悪ケースの多項式時間アルゴリズムがすでに知られている問題に焦点を当てていました。^[3] 1973 年に、ドナルド・クヌース^{[4] は}、ソートや中央値検索など、最悪ケースの多項式時間で解決可能な問題に対するアルゴリズムの平均ケースのパフォーマンスを広範囲に調査した「 Art of Computer Programming」の第 3 巻を出版しました。

$NP$ 完全問題に対する効率的なアルゴリズムは、一般的に、すべての入力に対して多項式時間で実行されるアルゴリズムとして特徴付けられます。これは、効率的な最悪ケースの複雑さを要求することと同じです。ただし、「少数の」入力に対して非効率的なアルゴリズムは、実際に発生する「ほとんどの」入力に対しては効率的である可能性があります。したがって、平均ケースの複雑さが最悪ケースの複雑さと異なる可能性があるこれらのアルゴリズムの特性を研究し、2 つを関連付ける方法を見つけることが望ましいです。

平均ケース複雑度の基本概念は、1986年にレオニード・レビンによって開発されました。彼は平均ケース複雑度と完全性を定義し、 $NP$ の平均ケース類似体である $distNP$ の完全問題の例を示した1ページの論文^[5]を発表しました。

定義

効率的な平均ケースの複雑さ

最初のタスクは、「平均して」効率的なアルゴリズムが何を意味するのかを正確に定義することです。最初の試みでは、効率的な平均ケースアルゴリズムを、考えられるすべての入力に対して期待される多項式時間で実行されるアルゴリズムと定義するかもしれません。このような定義にはさまざまな欠点があり、特に、計算モデルの変更に対して堅牢ではありません。たとえば、アルゴリズム $A$ が入力 $xに対して$ $t A (x)$ の時間で実行され、アルゴリズム $B が$ 入力 $xに対して$ $t$ $A$ $($ $x$ $)$ $2$ の時間で実行されるとします。つまり、 $B は$ $A$ よりも 2 乗で遅いということです。直感的には、平均ケースの効率性の定義は、 $B$ が平均して効率的である場合に限り、 $A$ が平均して効率的であるという考えをとらえる必要があります。ただし、入力が長さ $n$ の文字列の一様分布からランダムに抽出され、 $A$ $が$ $2$ $n の$ 時間がかかる文字列 $1$ $n を$ 除くすべての入力に対して $n$ $2 の$ 時間で実行されるとします。すると、 $Aの予想実行時間は多項式であるが、$ $B$ の予想実行時間は指数関数的であることが簡単に確認できます。^[3]

平均ケースの効率をより堅牢に定義するには、アルゴリズム $A が$ いくつかの入力に対して多項式時間よりも長く実行できるようにし、 $A$ がますます長い実行時間を必要とする入力の割合がますます小さくなるようにすることが理にかなっています。この直感は、実行時間と入力の割合の間の多項式トレードオフのバランスをとる、平均多項式実行時間の次の式に表れています。

\Pr _{x\in _{R}D_{n}}\left[t_{A}(x)\geq t\right]\leq {\frac {p(n)}{t^{\epsilon }}}

$任意のn 、 t > 0$ 、多項式 $p$ に対して、 $t A (x)は$ 入力 $xに対するアルゴリズム$ $A$ の実行時間を表し、 $εは$ 正の定数値である。^[6]あるいは、次のように書くこともできる。

E_{x\in _{R}D_{n}}\left[{\frac {t_{A}(x)^{\epsilon }}{n}}\right]\leq C

定数 $C$ と $ε$ に対して、 $n = | x |$ となる。^[7]言い換えれば、アルゴリズム $Aが$ $t A (n)$ ステップ実行した後、 $a$ を除くすべての問題を解くことができる場合、アルゴリズム A は平均ケースの複雑度が良好であると言える $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}。nc/( t A ( n )) ε⁠$ $長さn$ の入力の割合、ある ε に対して $c$ $> 0 。$ [^3]

分配問題

次のステップは、特定の問題に対する「平均」入力を定義することです。これは、各問題の入力を特定の確率分布に関連付けることによって実現されます。つまり、「平均ケース」問題は、言語 $L$ と、ペア $($ $L$ $、$ $D$ $)$ を形成する関連する確率分布 $D$ で構成されます。^[7]許可される分布の最も一般的な 2 つのクラスは次のとおりです。

多項式時間で計算可能な分布（ $P$ $計算可能）：これは、任意の入力x$ の累積密度を計算できる分布です。より正式には、確率分布 $μ$ と文字列 $x \in {0, 1} n$ が与えられた場合、多項式時間で値を計算できます。これは、 $Pr[$ $x$ $]$ も多項式時間で計算可能であることを意味します。 $\mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr[y]$
多項式時間サンプリング可能分布 ( $P$ サンプリング可能): これらは多項式時間でランダムなサンプルを抽出できる分布です。

これら2つの定式化は似ているものの、同等ではありません。分布が $P計算可能であれば$ $P$ サンプリングも可能ですが、 $P$ ≠ $P #P$ の場合は逆は成り立ちません。^[7]

AvgP と distNP

分布問題 $（ L 、 D ）は、上で定義したように、$ $L$ に対して効率的な平均ケースアルゴリズムが存在する場合、複雑性クラス $AvgP$ に属します。クラス $AvgPは$ 、文献では $distP$ と呼ばれることもあります。 ^[7]

分布問題 $（ L 、 D ）は、$ $Lが$ $NP$ に属し、 $D$ が $P$ 計算可能である場合、複雑性クラス $distNP$ $に属します。Lが$ $NP$ に属し、 $Dが$ $P$ サンプリング可能である場合、 $（$ $L$ $、$ $D$ $）は$ $sampNP$ に属します。^[7]

$AvgP$ と $distNPは$ それぞれ $P$ と $NP$ の平均ケース類似物を定義します。^[7]

分配問題間の削減

$(L, D)$ と $(L', D')$ を2つの分布問題とする。 $(L, D)$ 平均ケースは、任意の $n$ に対して、入力 $xがnの多項式時間で計算できる関数$ $f$ が存在する場合、 $(L', D')$ （ $(L, D) \leq AvgP (L', D')$ と表記 $）$ に簡約される。

(正しさ) $x \in L$ であるとき、かつその場合に限り、 $f (x) \in L'$
（支配）多項式 $p$ と $mが$ 存在し、任意の $n$ と $y$ に対して、 $\sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)$

支配条件は、問題 $(L 、 D)$ が平均的に困難である場合、 $(L' 、 D')$ も平均的に困難であるという考えを強制する。直感的には、簡約は問題 $Lのインスタンス$ $x を$ 解く方法を提供するはずであり、そのためには $f$ $($ $x$ $)$ を計算し、その出力を $L' を解くアルゴリズムに渡す必要がある。支配条件がなければ、これは不可能かもしれない。なぜなら、平均して多項式時間で$ $L を$ 解くアルゴリズムは少数の入力に対しては超多項式時間を要するかもしれないが、 $f はこれらの入力をはるかに大きな$ $D'$ のセットにマッピングする可能性があり、その結果アルゴリズム $A' は平均して多項式時間で実行できなくなるからである。支配条件は、そのような文字列が$ $D'$ 内で多項式的に出現することだけを許可する。^[6]

DistNP完全問題

$NP$ 完全性の平均ケース類似物は $distNP$ 完全性である。分布問題 $(L', D')$ が $distNP$ 完全であるとは、 $(L', D')が$ $distNP$ に含まれ、 $distNP$ 内のすべての $(L, D)$ に対して、 $($ $L$ $,$ $D$ $)$ が平均ケースで $($ $L'$ $,$ $D'$ $)$ に還元可能であることを意味する。^[7]

$distNP$ 完全問題の例としては、有界停止問題 $(BH 、 D)$ (任意の $P$ 計算可能なDについて) が挙げられ、これは次のように定義されます。

$BH=\{(M,x,1^{t}):M{\text{ は、}}x{\text{ を}}\leq t{\text{ ステップで受け入れる非決定性チューリングマシンです}}\}$ ^[7]

レビンはオリジナルの論文で、平均ケース $NP$ 完全である分布タイル問題の例を示しました。^[5]既知の $distNP$ 完全問題の調査はオンラインで入手できます。^[6]

活発に研究されている分野の 1 つに、新しい $distNP$ 完全問題を見つけることが挙げられます。しかし、そのような問題を見つけることは、平坦な分布を持つ分布問題は $EXP$ = $NEXP$ $でない限りdistNP$ 完全ではないという Gurevich の結果により複雑になる可能性があります。^[8] (平坦な分布 $μ$ とは、任意の $xに対して$ $μ$ $($ $x$ $) \leq 2$ $-|$ $x$ $|$ $ε$ となるような $ε$ $> 0 が$ 存在する分布です。) Livne の結果は、すべての自然な $NP$ 完全問題に $DistNP$ 完全バージョンがあることを示しました。^{[9]しかし、} $DistNP$ 完全な自然な分布問題を見つけるという目標はまだ達成されていません。^[10]

アプリケーション

ソートアルゴリズム

上で述べたように、平均計算量に関する初期の研究の多くは、ソートなど、多項式時間アルゴリズムがすでに存在する問題に焦点を当てていました。たとえば、クイックソートなどのランダム性を利用するソートアルゴリズムの多くは、最悪の場合の実行時間が $O(n2)$ ですが、平均の場合の実行時間は $O(nlog (n))$ です。ここで、 $nは$ $ソート$ する入力の長さです。^[2]

暗号化

ほとんどの問題では、最悪のケースでは困難であると考えられる問題に対する効率的なアルゴリズムを見つけるために、平均ケースの複雑さの分析が行われます。しかし、暗号化アプリケーションではその逆が当てはまります。つまり、最悪のケースの複雑さは無関係です。代わりに、暗号化スキームを「破る」すべてのアルゴリズムの平均ケースの複雑さが非効率的であるという保証が必要です。^[11]

したがって、すべての安全な暗号化方式は、一方向性関数の存在に依存しています。^[3]一方向性関数の存在は未解決の問題ですが、候補となる一方向性関数の多くは、整数因数分解や離散対数の計算などの難しい問題に基づいています。候補関数が $NP$ 完全であることは望ましくないことに注意する必要があります。これは、最悪の場合に問題を解決するための効率的なアルゴリズムが存在しない可能性が高いことを保証するだけだからです。実際に必要なのは、ランダムな入力 (つまり、平均的なケース) に対して効率的なアルゴリズムが問題を解決できないという保証です。実際、整数因数分解問題と離散対数問題はどちらも $NP \cap$ $coNP$ にあり、したがって $NP$ 完全であるとは考えられていません。^{[7]すべての暗号化が} $NP$ における平均ケースの解決困難な問題の存在を前提としているという事実は、平均ケースの複雑性を研究する主な動機の 1 つです。

その他の結果

アンドリュー・ヤオの1978年の論文にあるヤオの原理は、幅広い計算問題において、硬い入力分布とその分布に適応した決定論的アルゴリズムの平均複雑度は、高速ランダム化アルゴリズムとその最悪の入力の予想される複雑度と同じであることを示しています。^[12]

1990年に、インパグリアッツォとレビンは、一様分布の下での $distNP$ 完全問題に対して効率的な平均ケースアルゴリズムが存在する場合、任意の多項式時間サンプリング可能分布の下での $NP$ ^{のすべての問題に対して平均ケースアルゴリズムが存在することを示しました。 [13]}この理論を自然分布問題に適用することは、未解決の問題として残っています。^[3]

1992年、ベン・デイビッドらは、 $distNP$ のすべての言語が平均して優れた決定アルゴリズムを持っている場合、平均して優れた検索アルゴリズムも持っていることを示した。さらに、彼らはこの結論がより弱い仮定の下で成り立つことを示している。NPのすべての言語が一様分布に関して平均して決定アルゴリズムにとって容易であれば $、$ 一様分布に関して検索アルゴリズムにとっても平均して容易である。^{[14]したがって、暗号の一方向性関数は、一様分布上の} $distNP$ 問題が平均して決定アルゴリズムにとって困難である場合にのみ存在することができる。

1993 年、ファイゲンバウムとフォートナウは、非適応ランダム削減では、一様分布の下での $distNP完全問題に対する平均的に優れたアルゴリズムの存在が、$ $NP$ のすべての問題に対する最悪ケースの効率的なアルゴリズムの存在を意味することを証明することは不可能であることを示した。^[15] 2003 年、ボグダノフとトレヴィサンは、この結果を任意の非適応削減に一般化した。^[16]これらの結果は、削減によって平均ケースの複雑さと最悪ケースの複雑さの間に何らかの関連を作ることはほとんど不可能であることを示している。^[3]

参照

参考文献

^ O. Goldreich と S. Vadhan、「最悪ケースと平均ケースの複雑性に関する特別号」、Comput. Complex. 16、325–330、2007 年。
^ ab コーメン、トーマス H.;ライザーソン、チャールズ E.、リベスト、ロナルド L.、スタイン、クリフォード (2009) [1990]。アルゴリズム入門 (第 3 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03384-4。
^ abcdef A. Bogdanov および L. Trevisan、「平均ケース複雑度」、理論計算機科学の基礎と動向、第 2 巻、第 1 号 (2006 年) 1–106 ページ。
^ D. Knuth, The Art of Computer Programming . 第3巻、Addison-Wesley、1973年。
^ ab L. Levin、「平均ケース完全問題」、SIAM Journal on Computing、vol. 15、no. 1、pp. 285–286、1986 年。
^ abc J. Wang、「平均ケースの計算複雑性理論」、複雑性理論回顧II、pp. 295–328、1997年。
^ abcdefghi S. Arora および B. Barak、「計算複雑性：現代的アプローチ」、ケンブリッジ大学出版局、ニューヨーク、NY、2009 年。
^ Y. Gurevich、「完全および不完全ランダム化 NP 問題」、Proc. 28th Annual Symp. on Found. of Computer Science、IEEE (1987)、pp. 111–117。
^ N. Livne、「すべての自然な NP 完全問題には平均ケース完全バージョンがある」、Computational Complexity (2010) 19:477。https://doi.org/10.1007/s00037-010-0298-9
^ O. Goldreich、「Levin の平均ケース複雑性理論に関する注記」、技術レポート TR97-058、計算複雑性に関する電子コロキウム、1997 年。
^ J. Katz および Y. Lindell、「現代暗号化入門 (Chapman and Hall/CRC 暗号化およびネットワークセキュリティシリーズ)」、Chapman and Hall/CRC、2007 年。
^ ヤオ、アンドリュー(1977)、「確率的計算: 複雑さの統一的測定に向けて」、第 18 回 IEEE コンピュータサイエンスの基礎に関するシンポジウム (FOCS) の議事録、pp. 222–227、doi :10.1109/SFCS.1977.24
^ R. Impagliazzo および L. Levin、「一様にランダムに選択するよりも優れた NP インスタンス生成方法はない」、第 31 回 IEEE コンピュータサイエンスの基礎に関するシンポジウムの議事録、812 ～ 821 ページ、1990 年。
^ S. Ben-David、B. Chor、O. Goldreich、および M. Luby、「平均ケース複雑度の理論について」、Journal of Computer and System Sciences、vol. 44、no. 2、pp. 193–219、1992 年。
^ J. Feigenbaum および L. Fortnow、「完全なセットのランダム自己還元可能性」、SIAM Journal on Computing、vol. 22、pp. 994–1005、1993 年。
^ A. Bogdanov および L. Trevisan、「NP 問題における最悪ケースから平均ケースへの縮約について」、第 44 回 IEEE コンピュータサイエンスの基礎に関するシンポジウムの議事録、308 ～ 317 ページ、2003 年。

さらに読む

平均的なケースの複雑さに関する文献には、次の研究が含まれます。

フランコ、ジョン（1986）、「充足可能性問題に対するアルゴリズムの確率的性能について」、情報処理レター、23（2）：103–106、doi：10.1016/0020-0190（86）90051-7。
レビン、レオニード（1986）、「平均ケース完全問題」、SIAM Journal on Computing、15（1）：285–286、doi：10.1137/0215020。
Flajolet, フィリップ; JS Vitter (1987 年 8 月)、アルゴリズムとデータ構造の平均ケース分析、Tech.レポート、Institut National de Recherche en Informatique et en Automatique、BP 105-78153 Le Chesnay Cedex France。
Gurevich, Yuri ; Shelah, Saharon (1987)、「ハミルトン経路問題の予想計算時間」、SIAM Journal on Computing、16 (3): 486–502、CiteSeerX 10.1.1.359.8982、doi :10.1137/0216034。
Ben-David, Shai; Chor, Benny ; Goldreich, Oded ; Luby, Michael (1989)、「平均ケース複雑度の理論について」、Proc. 21st Annual Symposium on Theory of Computing、Association for Computing Machinery、pp. 204–216。
グレヴィッチ、ユーリ（1991）、「平均ケース完全性」、コンピュータとシステム科学ジャーナル、42（3）：346–398、doi：10.1016/0022-0000（91）90007-R、hdl：2027.42/293071989年のドラフトも参照。
Selman, B.; Mitchell, D.; Levesque, H. (1992)、「SAT 問題の難しい分布と簡単な分布」、Proc. 10th National Conference on Artificial Intelligence、pp. 459–465。
シューラー、ライナー、山上智之 (1992)、「構造的平均ケース複雑度」、Proc. Foundations of Software Technology and Theoretical Computer Science、Lecture Notes in Computer Science、vol. 652、Springer-Verlag、pp. 128–139。
Reischuk, Rüdiger; Schindelhauer, Christian (1993)、「正確な平均ケース複雑度」、Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science、pp. 650–661。
Venkatesan, R.; Rajagopalan, S. (1992)、「行列およびディオファントス問題の平均ケースの扱いにくさ」、Proc. 24th Annual Symposium on Theory of Computing、Association for Computing Machinery、pp. 632–642。
Cox, Jim; Ericson, Lars; Mishra, Bud (1995)、多段三段論法の平均ケース複雑度(PDF)、技術レポート TR1995-711、ニューヨーク大学コンピュータサイエンス学部。
インパグリアッツォ、ラッセル（1995 年 4 月 17 日）、平均ケースの複雑性に関する個人的な見解、カリフォルニア大学サンディエゴ校。
Paul E. Black、「Θ」、Dictionary of Algorithms and Data Structures[オンライン]Paul E. Black 編、米国国立標準技術研究所。2004 年 12 月 17 日。2009 年 2 月 20 日に閲覧。
Christos Papadimitriou (1994)。計算複雑性。Addison-Wesley。

[gol07-1] O. Goldreich と S. Vadhan、「最悪ケースと平均ケースの複雑性に関する特別号」、Comput. Complex. 16、325–330、2007 年。

[clrs-2] コーメン、トーマス H.;ライザーソン、チャールズ E.、リベスト、ロナルド L.、スタイン、クリフォード (2009) [1990]。アルゴリズム入門 (第 3 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03384-4。

[bog06-3] A. Bogdanov および L. Trevisan、「平均ケース複雑度」、理論計算機科学の基礎と動向、第 2 巻、第 1 号 (2006 年) 1–106 ページ。

[knu73-4] D. Knuth, The Art of Computer Programming . 第3巻、Addison-Wesley、1973年。

[levin86-5] L. Levin、「平均ケース完全問題」、SIAM Journal on Computing、vol. 15、no. 1、pp. 285–286、1986 年。

[wangsurvey-6] J. Wang、「平均ケースの計算複雑性理論」、複雑性理論回顧II、pp. 295–328、1997年。

[ab09-7] S. Arora および B. Barak、「計算複雑性：現代的アプローチ」、ケンブリッジ大学出版局、ニューヨーク、NY、2009 年。

[gur87-8] Y. Gurevich、「完全および不完全ランダム化 NP 問題」、Proc. 28th Annual Symp. on Found. of Computer Science、IEEE (1987)、pp. 111–117。

[livne06-9] N. Livne、「すべての自然な NP 完全問題には平均ケース完全バージョンがある」、Computational Complexity (2010) 19:477。https://doi.org/10.1007/s00037-010-0298-9

[gol97-10] O. Goldreich、「Levin の平均ケース複雑性理論に関する注記」、技術レポート TR97-058、計算複雑性に関する電子コロキウム、1997 年。

[katz07-11] J. Katz および Y. Lindell、「現代暗号化入門 (Chapman and Hall/CRC 暗号化およびネットワークセキュリティシリーズ)」、Chapman and Hall/CRC、2007 年。

[12] ヤオ、アンドリュー(1977)、「確率的計算: 複雑さの統一的測定に向けて」、第 18 回 IEEE コンピュータサイエンスの基礎に関するシンポジウム (FOCS) の議事録、pp. 222–227、doi :10.1109/SFCS.1977.24

[imp90-13] R. Impagliazzo および L. Levin、「一様にランダムに選択するよりも優れた NP インスタンス生成方法はない」、第 31 回 IEEE コンピュータサイエンスの基礎に関するシンポジウムの議事録、812 ～ 821 ページ、1990 年。

[bd92-14] S. Ben-David、B. Chor、O. Goldreich、および M. Luby、「平均ケース複雑度の理論について」、Journal of Computer and System Sciences、vol. 44、no. 2、pp. 193–219、1992 年。

[ff93-15] J. Feigenbaum および L. Fortnow、「完全なセットのランダム自己還元可能性」、SIAM Journal on Computing、vol. 22、pp. 994–1005、1993 年。

[bog03-16] A. Bogdanov および L. Trevisan、「NP 問題における最悪ケースから平均ケースへの縮約について」、第 44 回 IEEE コンピュータサイエンスの基礎に関するシンポジウムの議事録、308 ～ 317 ページ、2003 年。