一般的なケースの複雑さ

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

一般的なケースの複雑度は、代表的でない入力の小さなセットを無視し、残りの入力に対して最悪のケースの複雑度を考慮することによって、計算問題の複雑度を測定する方法です。小さいとは、漸近密度の観点から定義されます。一般的なケースの複雑度の明らかな有効性は、さまざまな具体的な計算問題において、最も困難な事例はまれであるように思われることです。典型的な事例は比較的簡単です。

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

一般的なケースの複雑さの詳細な紹介は調査で見つけることができます。^{[2] [3]}

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

定義 1. I上のサイズ関数は無限の範囲を持つマップです。半径nの球はです。 ${\displaystyle \sigma :I\to \mathbb {N} }$${\displaystyle B_{n}=\{x\in I\mid \sigma (x)\leq n\}}$

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

を確率分布の集合とします。ここで は上の確率分布です。ボールが有限であれば、それぞれは最も一般的なケースである等確率分布と見なすことができます。空または を持つ は有限個だけであることに注意してください。これらは無視します。 ${\displaystyle \{\mu _{n}\}}$${\displaystyle \mu_{n}}$${\displaystyle B_{n}}$${\displaystyle B_{n}}$${\displaystyle \mu_{n}}$${\displaystyle B_{n}}$${\displaystyle \mu _{n}(B_{n})=0}$

定義 2.部分集合の漸近密度とは、この限界が存在する場合です。 ${\displaystyle X\subset I}$${\displaystyle \rho (X)=\lim _{n\to \infty }\mu _{n}(X\cap B_{n})}$

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

${\displaystyle \rho (X)=\lim {\frac {|X\cap B_{n}|}{|B_{n}|}}.}$

この場合、ボールの代わりに球体を使用して を定義すると便利なことがよくあります。シュトルツの定理を使用した議論では、が存在する場合が存在し、その場合、それらは等しいことが示されています。 ${\displaystyle I_{n}=\{x\in I\mid \sigma (x)=n\}}$${\displaystyle \rho '(X)=\lim {\frac {|X\cap I_{n}|}{|I_{n}|}}}$${\displaystyle \rho (X)}$${\displaystyle \rho '(X)}$

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

一般的なサブセットX は漸近的に大きくなります。X が実際に大きく見えるかどうかは、1に収束する速さによって決まります。超多項式収束は十分に速いようです。 ${\displaystyle \mu_{n}(X\cap B_{n})}$

定義 4 アルゴリズムがGenP (一般に多項式時間)に属するとは、誤った答えを決して出さず、一般的な入力セットに対して多項式時間で正しい答えを出す場合です。問題がGenPに属するとは、アルゴリズムがGenPに属する場合です。同様に、GenL (一般に線形時間)、GenE (一般に 線形指数を持つ指数時間) 、 GenExp (一般に指数時間) などにも当てはまります。 ExpGenPは、関連する汎用セットが指数的に汎用である GenPのサブクラスです。

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

定義 5.アルゴリズムが問題を一般的に解決するとは、間違った答えを決して出さず、一般的な入力セットに対して正しい答えを出す場合です。問題が一般的に解決可能であるとは、何らかのアルゴリズムによって一般的に解決できる場合です。

• 有名な決定不可能な問題：適切な仮定の下では、単語、共役、メンバーシップの決定問題は一般的に多項式である。^[1]
• 単語探索問題と共役探索問題は、すべての固定された有限提示群に対してGenPに含まれる。 ^[4]

• よく知られている剰余類列挙手続きは、一般的な入力集合に対して計算可能な上限を許容する。^[5]

• 自由群の1つの要素が自己同型によって別の要素にマッピングされるかどうかをテストするホワイトヘッドアルゴリズムは、最悪の場合の上限が指数関数的であるが、実際にはうまく動作する。このアルゴリズムはGenLであることが示される。^[6]
• HNN拡張における共役性問題は自由群に対しても解けない可能性がある。しかし、一般的には3次時間で解ける。^[7]

• 片面テープ付きチューリングマシンの停止問題は、ほとんどの場合簡単に解決できます。これはGenP ^{[8]にあります。}

両面テープの状況は不明である。しかし、両方のタイプのマシンにはある種の下限がある。停止問題は、どのチューリングマシンモデルでもExpGenPには存在しない。 ^{[9] [10]}

• ポスト対応問題はExpGenPにあります。^[2]

プレスブルガー算術の決定問題では、二重指数関数の最悪ケースの下限値^{[11]と三重指数関数の最悪ケースの上限値が許容される。一般的な複雑さは不明だが、この問題は}ExpGenPには含まれないことがわかっている。^[12]

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

• 3つの充足可能性問題はExpGenPにある。^[13]
• 部分集合和問題はGenPにある。^[2]

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

一連の論文^{[15] [16] [17]は、}編組群に関する仮定に基づいて安全性が保証されているAnshel-Anshel-Goldfeld鍵交換プロトコルの暗号解読に焦点を当てています。この一連の論文は、MiasnikovとUshakov (2008) ^[18]で最高潮に達します。彼らは、一般的なケースの複雑さからのテクニックを適用して、長さベースの攻撃とそれが機能する条件の完全な分析を得ています。一般的な観点からは、商攻撃と呼ばれる一種の新しい攻撃と、Anshel-Anshel-Goldfeldプロトコルのより安全なバージョンも示唆されています。

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

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

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

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

定理 3 一般的な複雑性クラスには無限の階層があります。より正確には、適切な複雑性関数fの場合、です。 ${\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}}}$${\displaystyle T:I\to \mathbb {N} }$${\displaystyle \mu}$${\displaystyle {\mathcal {A}}}$

例 1を上のすべての単語の集合とし、サイズを単語長 と 定義します。を長さnの単語の集合と定義し、それぞれを等確率測度と仮定します。各 内の 1 つの単語を除くすべての単語について、また例外的な単語については T(w)=n であると仮定します。${\displaystyle \{0,1\}}$${\displaystyle \sigma (w)}$${\displaystyle |w|}$${\displaystyle I_{n}}$${\displaystyle \mu_{n}}$${\displaystyle I_{n}}$${\displaystyle T(w)=2^{2^{n}}}$

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

例 2 Iと は前と同じままですが、と を 定義します。T は、典型的な入力では指数関数的ですが、平均すると多項式になります。TはGenPにはありません。 ${\displaystyle \sigma (w)=|w|}$${\displaystyle \mu (w)=2^{-2|w|-1}}$${\displaystyle T(w)=2^{|w|}}$

これら2つの例では、一般的な複雑さは、平均的なケースの複雑さよりも、典型的な入力に対する動作に密接に関連しています。平均的なケースの複雑さは、別のものを測定します。つまり、困難なインスタンスの頻度と難易度のバランスです。^{[21] [22]} 大まかに言えば、平均して多項式時間のアルゴリズムは、計算に超多項式時間を必要とする入力のサブ多項式部分しか持つことができません。

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

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

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

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

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