平均時計算量理論の概要
概要
平均時計算量とは、計算問題に対してそれが効率的に解ける入力の割合を研究する分野である。 研究対象の性質上、問題と入力分布のペア(しばし分布問題と呼ばれる)を考える。 効率的なアルゴリズム(例えば多項式時間アルゴリズム)が、入力分布に従って生成された入力に対して正解する確率(成功確率)を考え、成功確率が最大となるようなアルゴリズムやその限界について理解することが目標となる。 具体的な問題としては埋め込みクリーク問題やLWE問題などを考える。 大まかに分けて平均時計算量は二つの文脈で研究されている。
計算量的擬似ランダムネスとその応用。 効率的に解ける入力が少なければ少ないほど、その問題の困難性は強いとみなし、強い困難性を持つ判定問題は計算量的擬似ランダム性を通じて暗号学的プリミティブの構成や乱択アルゴリズムの脱乱択化といった応用を持つ。 統計的には、$ \{0,1\}^n $ 上で一様ランダムに選ばれた$x$と任意の関数$f\colon \{0,1\}^n\to \{0,1\}$に対して、$(x,f(x))$の情報論的エントロピーは$n$ビットである（つまり、ランダム文字列に$f$を適用してもエントロピーは増えない）。 しかし、$f\colon \{0,1\}^n\to \{0,1\}$が強い困難性を持つ関数ならば、任意の効率的なアルゴリズムにとって、$x$から$f(x)$を推定するのは難しいので、$f(x)$は$x$とは独立なランダムビットに見える。従って$(x,f(x))$の計算量的エントロピーは$n+1$ビットとなる。 このように、驚くべきことに、強い困難性を持つ問題があれば、計算量的なエントロピーを増幅させられる。 そして、そのような問題を構成するための手法として誤り訂正符号やエクスパンダーグラフなどの組合わせ的、代数的な概念が積極的に応用されている。
求解における情報理論と計算量理論のギャップ。 高次元統計学の文脈では最尤推定法で解ける具体的な問題に対し、それが計算量的の意味で効率的に解けるかどうかが議論される。 例えば埋め込みクリーク問題では、$n$頂点ランダムグラフのランダムな位置に埋め込まれた$k$-クリークを探し出せという問題を考える。 クリークサイズが$k\gg \log n$であれば、高確率でランダムグラフが$k$-クリークを含まないので、$k$頂点部分集合を列挙することにより探索することができる。 しかしながら現在のところ、埋め込みクリーク問題を解く多項式時間アルゴリズムは$k\ge \sqrt{n}$の範囲でしか見つかっておらず、$\log n \ll k \ll \sqrt{n}$の範囲でこの問題が解けるかどうかは重要な未解決問題とされている。 また、埋め込みクリーク問題の計算量的下界を仮定すると、圧縮センシング、分布の性質検査、あるゲームのナッシュ均衡の近似、主成分分析など様々な実用的な問題に対する計算量下界が導出できることが知られている。