一般的なケースの複雑さ

一般的なケースの複雑性は、計算複雑性理論のサブフィールドであり、「ほとんどの入力」における計算問題の複雑性を研究します。

一般的なケースの複雑度とは、計算問題の複雑度を測定する方法の一つであり、代表的でない少数の入力を無視し、残りの入力については最悪のケースの複雑度を考慮する。「小さい」とは、漸近密度によって定義される。一般的なケースの複雑度が明らかに有効であるのは、様々な具体的な計算問題において、最も困難な事例は稀であるように見えるためである。典型的な事例は比較的容易である。

複雑性へのこのアプローチは、前世紀初頭に遡る計算の伝統を持つ組合せ群論に端を発しています。一般複雑性の概念は2003年の論文[1]で導入され、著者らは有限生成群の大規模なクラスに対して、組合せ群論におけるいくつかの古典的な決定問題、すなわち単語問題、共役問題、帰属問題、の一般時間複雑性が線形であることを示しました。

一般的なケースの複雑さの詳細な紹介は調査でご覧いただけます。[2] [3]

基本的な定義

漸近密度

計算問題に対する無限の入力 集合をIとします。

定義1. I上のサイズ関数は無限値域を持つ写像である。半径nの球体はである。 σ : 私 → 北 {\displaystyle \sigma :I\to \mathbb {N} } B n ＝ { × ∈ 私 ∣ σ （ × ） ≤ n } {\displaystyle B_{n}=\{x\in I\mid \sigma (x)\leq n\}}

入力が有限のアルファベット上の文字列としてコード化されている場合、サイズは文字列の長さになる可能性があります。

を確率分布の集合とし、は上の確率分布とする。球が有限個であれば、それぞれは等確率分布とみなすことができ、これが最も一般的なケースである。空または を持つ は有限個しかないことに注意する。これらは無視する。 { μ n } {\displaystyle \{\mu _{n}\}} μ n {\displaystyle \mu_{n}} B n {\displaystyle B_{n}} B n {\displaystyle B_{n}} μ n {\displaystyle \mu_{n}} B n {\displaystyle B_{n}} μ n （ B n ） ＝ 0 {\displaystyle \mu _{n}(B_{n})=0}

定義 2.サブセットの漸近密度とは、この限界が存在する場合 です。 X ⊂ 私 {\displaystyle X\subset I} ρ （ X ） ＝ リム n → ∞ μ n （ X ∩ B n ） {\displaystyle \rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})}

ボールが有限で等確率測度である場合、 B n {\displaystyle B_{n}} μ n {\displaystyle \mu_{n}}

ρ （ X ） ＝ リム | X ∩ B n | | B n | 。 {\displaystyle \rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.}

この場合、ボールの代わりに球体を用いて を定義すると便利な場合が多い。シュトルツの定理を用いた議論は、 が存在する場合 が存在し、その場合それらは等しいこと を示す。 私 n ＝ { × ∈ 私 ∣ σ （ × ） ＝ n } {\displaystyle I_{n}=\{x\in I\mid \sigma (x)=n\}} ρ ′ （ X ） ＝ リム | X ∩ 私 n | | 私 n | {\displaystyle \rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}} ρ （ X ） {\displaystyle \rho (X)} ρ ′ （ X ） {\displaystyle \rho '(X)}

定義 3 は、 の場合には汎用的であり、 の場合には無視できます。 定義 2 の極限への収束が指数的（超多項式的）に速い場合、 Xは指数的（超多項式的）に汎用的となります。 X ⊆ 私 {\displaystyle X\subseteq I} ρ （ X ） ＝ 1 {\displaystyle \rho (X)=1} ρ （ X ） ＝ 0 {\displaystyle \rho (X)=0}

一般的な部分集合Xは漸近的に大きい。Xが実際に大きいように見えるかどうかは、Xが1に収束する速さに依存します。超多項式収束は十分に速いと思われます。 μ n （ X ∩ B n ） {\displaystyle \mu_{n}(X\cap B_{n})}

一般的な複雑性クラス

定義4 アルゴリズムがGenP （一般多項式時間）に属するとは、誤った答えを一度も出さず、かつ、一般的な入力集合に対して多項式時間で正しい答えを出すことを意味します。問題がGenPに属するとは、その問題がGenPに属するアルゴリズムを許容することを意味します。同様に、 GenL（一般線形時間）、GenE（一般 線形指数を持つ指数時間） 、 GenExp（一般指数時間）など にも当てはまります。ExpGenPは、関連する一般集合が指数的に一般となる GenPのサブクラスです。

より一般的には、任意の入力に対して、一般的な入力セットの 時間計算量O ( f )に対応する クラスGen(f)を定義できます。 f : 北 → 北 {\displaystyle f:\mathbb {N} \to \mathbb {N} }

定義5.あるアルゴリズムが問題をジェネリックに解くとは、誤った答えを一度も出さず、かつ一般的な入力に対して正しい答えを出すことを意味する。ある問題がジェネリックに解けるとは、あるアルゴリズムによってジェネリックに解けることを意味する。

理論と応用

組合せ群論の問題

  • 有名な決定不可能問題：適切な仮定の下では、語、共役、所属の決定問題は一般に多項式である。[1]
  • 単語探索問題と共役探索問題は、すべての固定された有限提示群に対してGenPに含まれる。 [4]
  • よく知られている剰余類列挙手続きは、一般的な入力集合に対して計算可能な上限を許容する。[5]
  • 自由群の1つの元が自己同型写像​​によって別の元に写像されるかどうかを判定するホワイトヘッドアルゴリズムは、最悪のケースでは指数関数的な上限値を持つものの、実際には良好に動作する。このアルゴリズムはGenLに属することが示されている。[6]
  • HNN拡張における共役性問題は、自由群に対してさえも解けない可能性がある。しかし、一般的には3乗時間で解ける。[7]

停止問題と郵便対応問題

両面テープの状況は不明である。しかし、どちらのタイプの機械にもある種の下限が存在する。ExpGenPでは、チューリング機械のどのモデルに対しても停止問題は存在しない。 [ 9] [10]

プレスブルガー算術

プレスブルガー算術の決定問題は、最悪のケースでは二重指数関数的な下限値[11] 、最悪のケースでは三重指数関数的な上限値を持つ。ジェネリック計算量は不明だが、この問題はExpGenPには含まれないことが分かっている。[12]

NP完全問題

NP 完全問題は平均的には簡単であることはよく知られているため、NP 完全問題のいくつかが一般的にも簡単であることは驚くことではありません。

一方向関数

一方向関数の一般的な複雑性バージョン[14]があり、これは同じクラスの関数を生成しますが、通常とは異なるセキュリティの仮定を考慮することができます。

公開鍵暗号

一連の論文[15] [16] [17]は、アンシェル・アンシェル・ゴールドフェルド鍵交換プロトコルの暗号解読に焦点を当てています。このプロトコルの安全性は、組紐群に関する仮定に基づいています。この一連の論文は、ミアスニコフとウシャコフ（2008）[18]で最高潮に達します。彼らは、一般的なケース複雑性の手法を適用し、長さに基づく攻撃とその動作条件の完全な解析を行っています。この一般的な観点からは、商攻撃と呼ばれる新しい種類の攻撃と、アンシェル・アンシェル・ゴールドフェルドプロトコルのより安全なバージョンも示唆されています。

一般的な理論的結果のリスト

  • 有名なライスの定理は、 Fがからまでの部分計算可能関数の集合の部分集合である場合、 Fまたはその補集合が空でない限り、特定のチューリングマシンがF内の関数を計算できるかどうかを判定する問題は決定不可能である、というものである。次の定理は、その一般的なバージョンである。 北 {\displaystyle \mathbb {N} } { 0 、 1 } {\displaystyle \{0,1\}}

定理1 [19] Iをすべてのチューリングマシンの集合とする。Fが、Fとその補集合がともに空でないような、 Fからそれ自身への部分計算可能な関数全体の集合の部分集合である場合、与えられたチューリングマシンがFから関数を計算できるかどうかを決定する問題は、 Iの任意の指数的ジェネリック部分集合上では決定可能ではない。 北 {\displaystyle \mathbb {N} }

  • 以下の定理は[1]からのものである。

定理 2一般的に計算可能な形式言語の集合は測度がゼロである。

定理3 ジェネリックな複雑性クラスには無限の階層が存在する。より正確には、真複雑性関数fの場合、となる。 G e n （ f ） ⊊ G e n （ f 3 ） {\displaystyle Gen(f)\subsetneq Gen(f^{3})}

次の定理は、分布NP問題の中に平均ケース完全問題が存在するのと同様に、一般ケース完全問題も存在することを示しています。一般ケースにおける議論は平均ケースにおける議論と類似しており、一般ケース完全問題は平均ケース完全でもあります。これは分布有界停止問題です。

定理4 [2]分布NP問題のクラス内で分布有界停止問題が完全となるような一般多項式時間縮約の概念がある。

以前の研究との比較

ほぼ多項式時間

マイヤーとパターソン[20]は、サイズnのp(n)入力を除くすべての入力に対してp(n)ステップ 以内で停止するアルゴリズムをほぼ多項式時間、すなわちAPTであると定義しています。明らかに、APTアルゴリズムはGenPクラスに含まれます。GenPにはNP完全問題がいくつか見られましたが、マイヤーとパターソンはAPTではそうではないことを示しています。彼らは、NP完全問題がAPTの問題に還元可能であるのはP = NPの場合のみであることを証明しています。したがって、APTはGenPよりもはるかに制限が厳しいようです。

平均的なケースの複雑さ

一般的なケースの複雑度は平均ケースの複雑度に似ています。しかし、いくつか重要な違いがあります。一般的なケースの複雑度は、ほとんどの入力に対するアルゴリズムのパフォーマンスを直接的に表す指標であるのに対し、平均ケースの複雑度は、容易なケースと困難なケースのバランスを示す指標です。さらに、一般的なケースの複雑度は、当然ながら決定不能問題にも適用されます。

が平均して多項式時間計算量 であるアルゴリズムであるとします。典型的な入力に対する の挙動について何が推測できますか？ あ {\displaystyle {\mathcal {A}}} T : 私 → 北 {\displaystyle T:I\to \mathbb {N} } μ {\displaystyle \mu} あ {\displaystyle {\mathcal {A}}}

例1上のすべての単語の集合をIとし、その大きさを単語長と 定義する。長さnの単語の集合をIとし、各単語を等確率測度とする。各単語において、1つの単語を除くすべての単語についてT(w)=nとし、例外的な単語については T(w)=nとする。 { 0 、 1 } {\displaystyle \{0,1\}} σ （ わ ） {\displaystyle \sigma (w)} | わ | {\displaystyle |w|} 私 n {\displaystyle I_{n}} μ n {\displaystyle \mu_{n}} 私 n {\displaystyle I_{n}} T （ わ ） ＝ 2 2 n {\displaystyle T(w)=2^{2^{n}}}

この例では、Tは典型的な入力に対しては確かに多項式ですが、平均的には多項式ではありません。TはGenPにあります。

例 2 Iと は前と同じままですが、と を定義します。T は、典型的な入力に対しては指数関数的ですが、平均的には多項式です。TはGenPには存在しません。 σ （ わ ） ＝ | わ | {\displaystyle \sigma (w)=|w|} μ （ わ ） ＝ 2 − 2 | わ | − 1 {\displaystyle \mu (w)=2^{-2|w|-1}} T （ わ ） ＝ 2 | わ | {\displaystyle T(w)=2^{|w|}}

これら2つの例において、一般的な複雑度は、平均的なケースの複雑度よりも、典型的な入力に対する動作と密接に関連しています。平均的なケースの複雑度は、別のもの、つまり困難なインスタンスの頻度と難易度のバランスを測る指標です。[21] [22] 大まかに言えば、平均的に多項式時間で計算できるアルゴリズムは、超多項式時間を要する入力が多項式以下の割合しか持たない可能性があります。

しかしながら、一般的なケースと平均的なケースの複雑さが互いに非常に近い場合もある。関数が球面上の -平均多項式であるとは、 が存在することであり、ここで は によって誘導される集合である。f が球面上の -平均多項式である場合、 f は-平均多項式であり、多くの分布に対して逆が成り立つ [23]。 f : 私 → R + {\displaystyle f:I\rightarrow\mathbb{R}^{+}} μ {\displaystyle \mu} け ≥ 1 {\displaystyle k\geq 1} ∑ わ ∈ 私 n f 1 / け （ わ ） μ n （ わ ） ＝ お （ n ） {\displaystyle \sum _{w\in I_{n}}f^{1/k}(w)\mu _{n}(w)=O(n)} { μ n } {\displaystyle \{\mu _{n}\}} μ {\displaystyle \mu} μ {\displaystyle \mu} μ {\displaystyle \mu}

定理5 [2]関数が球面上の -平均に関して多項式である場合、 fは 球面漸近密度に関して一般に多項式である。 f : 私 → R + {\displaystyle f:I\rightarrow\mathbb{R}^{+}} μ {\displaystyle \mu} ρ ′ {\displaystyle \rho '}

定理6 [2]完全アルゴリズムが指数関数的時間境界Tを持ち、 同じ問題に対する部分アルゴリズムが、 入力Iに対する確率測度に対応するアンサンブルに関してExpGenPに属すると仮定する。このとき、平均時間計算量である完全アルゴリズムが存在する。 あ {\displaystyle {\mathcal {A}}} B {\displaystyle {\mathcal {B}}} { μ n } {\displaystyle \{\mu _{n}\}} μ {\displaystyle \mu} あ {\displaystyle {\mathcal {A}}} μ {\displaystyle \mu}

エラーのないヒューリスティックアルゴリズム

2006年の論文で、ボグダノフとトレヴィサンは、一般的なケースの複雑さの定義に近づいた。[24] 彼らは部分的なアルゴリズムの代わりに、いわゆるエラーレス・ヒューリスティック・アルゴリズムを考察している。これらは完全なアルゴリズムであり、「？」を出力して停止することで失敗する可能性がある。クラスAvgnegPは、多項式時間で実行され、失敗確率が無視できる、すなわち超多項式的に速く0に収束する すべてのエラーレス・ヒューリスティック・アルゴリズムAから構成されるように定義される。AvgnegPはGenPのサブセットである。エラーレス・ヒューリスティック・アルゴリズムは、インパグリアッツォによって定義された良性障害アルゴリズムと本質的に同じであり、平均多項式時間アルゴリズムは、いわゆる良性アルゴリズム・スキームの観点から特徴付けられる。 私 n {\displaystyle I_{n}}

参照

  • 平滑化分析- 同様の概念: 平均実行時間の最悪のケースを測定します。

参考文献

  1. ^ abc I. Kapovich、A. Myasnikov、P. Schupp、V. Shpilrain、「一般的なケースの複雑さ、群論とランダムウォークにおける決定問題」、J. Algebra、vol 264 (2003)、665–694。
  2. ^ abcdef R. Gilman、AG Miasnikov、AD Myasnikov、および A. Ushakov、Generic Case Complexity、未出版の本の初稿、143 ページ。
  3. ^ R. Gilman、AG Miasnikov、AD Myasnikov、A. Ushakov、「一般的なケースの複雑さに関する報告書」、オムスク大学のヘラルド、特別号、2007年、103-110。
  4. ^ A. Ushakov、論文、ニューヨーク市立大学、2005年。
  5. ^ R. Gilman、「群論における難しい問題」、群論および半群論における幾何学的および組合せ的手法に関する国際会議での講演、2009 年 5 月 18 日。
  6. ^ I. Kapovich, P. Schupp, V. Shpilrain, Whiteheadsアルゴリズムの一般的性質とランダム1関係群の同型性剛性, Pacific J. Math. 223 (2006)
  7. ^ AV Borovik, AG Myasnikov, VN Remeslennikov, HNN拡張における共役問題の一般的な複雑性とミラー群のアルゴリズム的階層化, Internat. J. Algebra Comput. 17 (2007), 963–997.
  8. ^ JD HamkinsとA. Miasnikov、「停止問題は漸近確率1の集合上で決定可能である」、Notre Dame J. Formal Logic 47 (2006)、515–524。
  9. ^ A. MiasnikovとA. Rybalov、「決定不能な問題の一般的な複雑性」、Journal of Symbolic Logic 73 (2008)、656–673。
  10. ^ A. Rybalov,停止問題の強力に一般的な決定不可能性について, Theoret. Comput. Sci. 377 (2007), 268–270.
  11. ^ MJ FischerとMO Rabin、「Presburger算術の超指数的複雑性」、SIAM-AMS応用数学シンポジウムの議事録7 (1974) 2741。
  12. ^ A. Rybalov、「プレスブルガー算術の一般的な複雑さ」、356–361、ロシアにおける第2回コンピュータサイエンスに関する国際シンポジウム、CSR 2007、コンピュータサイエンスの講義ノート4649、Springer 2007。
  13. ^ R. Gilman、AG Miasnikov、AD Myasnikov、およびA. Ushakov、「一般的なケースの複雑さに関するレポート」、オムスク大学のヘラルド、特別号、2007年、103-110。
  14. ^ AD Myasnikov、「一般的な複雑性と一方向性関数」、グループ、複雑性、暗号化、1、(2009)、13–31。
  15. ^ R. Gilman、AG Miasnikov、AD Myasnikov、A. Ushakov、「新しいコミュテータ鍵交換の開発」、Proc. First Int. Conf. on Symbolic Computation and Cryptography (SCC-2008)、北京、2008年。
  16. ^ AG Myasnikov、V. Shpilrain、A. Ushakov、「編組グループベースの暗号化プロトコルに対する実際的な攻撃」、Lecture Notes in Computer Science、3621、Springer Verlag、2005、86–96。
  17. ^ AD Myasnikov、A. Ushakov、「長さベースの攻撃と編組グループ：Anshel–Anshel–Goldfeld鍵交換プロトコルの暗号解析」、Public Key Cryptography PKC 2007、76–88、Lecture Notes in Comput. Sci.、4450、Springer、ベルリン、2007年。
  18. ^ AG MiasnikovとA. Ushakov、「ランダムサブグループと長さベース攻撃および商攻撃の分析」、Journal of Mathematical Cryptology、2 (2008)、29–61。
  19. ^ A. MiasnikovとA. Rybalov、「決定不能な問題の一般的な複雑性」、Journal of Symbolic Logic 73 (2008)、656–673。
  20. ^ AR Meyer と MS Paterson、「明らかに解決困難な問題はどの程度の頻度で解決困難になるのか?」、MIT 技術レポート、MIT/LCS/TM-126、1979 年 2 月。
  21. ^ Y. Gurevich、「チャレンジャーソルバーゲーム：P =?NPのテーマのバリエーション」、Logic in Computer Science コラム、The Bulletin of the EATCS、1989年10月、p.112-121。
  22. ^ R. Impagliazzo、「平均ケースの複雑性に関する個人的な見解」、第 10 回年次構造複雑性理論会議 – SCT 1995 の議事録、IEEE コンピュータ協会、1995 年、134 ページ。
  23. ^ Y. Gurevich、「平均ケース完全性」、Journal of Computer and System Science、42 (1991)、346–398。
  24. ^ A. Bogdanov, L. Trevisan, Average-case Complexity , Found. Trends Theor. Comput. Sci. 2 , No. 1, 111 p. (2006).
「https://en.wikipedia.org/w/index.php?title=Generic-case_complexity&oldid=1317505583」より取得