NP証明の一様サンプリング（続き）

研究

前回のエントリの続きです．

言語 L\in{\rm NP}に対してそのYESインスタンス x\in Lを入力として与えられたときに，その xに対する証明集合[tex: R_x = \{ w\in\{0,1\}^m: \in B_L \}] （ mは n=|x|の多項式， B_L\in Pは Lについて与えられたインスタンスと証明の二項関係）から一様ランダムに取ってくる {\rm NP}オラクル付き多項式時間乱択アルゴリズムの設計が目標です．

大まかな流れは以下の通りです．

  1. ランダムなハッシュ（実際には m-wise independent hash） h:\{0,1\}^m\rightarrow\{0,1\} を選び，条件「異なる w_1,...,w_{2m^2}\in\{0,1\}^mが存在して w_1,...,w_lが xの証明でかつ h(w_1)=\cdots=h(w_l)が成立する」か k=nとなるまで，ハッシュの値域を制御するパラメータ kを0から開始して1づつ増加させながらこのランダムなハッシュ選択を繰り返す．ここで l = poly(m)である．
  2. 一様ランダムに \alpha\in\{0,1\}^kから選んでその逆像 h^{-1}(\alpha)=\{w_1,...,w_{l'}\}を全て列挙し，それらの中から一様ランダムに要素を選んで出力する．

ステップ2で適当なハッシュ関数 h:\{0,1\}^m\rightarrow\{0,1\}^kが選べたときの状況が下の図です．ここでポイントなのは，まずランダムなハッシュを持ってきて良く分からない集合を潰したときに，その逆像のサイズは高い確率である程度揃っているという点です．そのサイズが多項式で押さえられればNPオラクルで逆像のサイズをチェックしたり逆像を全て列挙することが可能となります．この辺は後でもう少し詳しく書きます．