ランダム3SATに対する固有値解法の解析
スポンサーリンク
概要
- 論文の詳細を見る
φを充足解に持つn変数のランダム3CNF論理式Iについて考える.Iはφによってi個のリテラルが真になるような節を独立に確率p_iで含むような3CNFである.本稿ではp_iをp_i=d_i logn/n^2とし,d_iがある定数d_<min>より大きく,d_1+d_2≠d_3となるとき,固有ベクトルを用いたアルゴリズムが(1-1/logn)n以上の変数に対してφと同じ割り当てを出力することを示した.
- 社団法人電子情報通信学会の論文
- 2008-09-04