MAX 3SATのランダムな例題生成
スポンサーリンク
概要
- 論文の詳細を見る
本論文ではNP完全問題の1つである3充足可能性問題3SATの最適化問題MAX3SATをとりあげる.この問題に対して, 最適解を高い確率で保証した例題を生成する例題生成アルゴリズムを提案し, 最適解を保証する確率が高くなるための条件を理論的に解析した.具体的にはO(u+nlnn+n√<ulnn>)程度の項数があれば, 高い確率で最適値uとなることを証明した.また, 実験的にも解析を試した.
- 2000-11-10
著者
関連論文
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- MAX 3SATのランダムな例題生成
- MAX-3SATの解の平均の解析
- 3充足可能性判定問題3SATの正例題生成手法の解析(並列処理)
- 3充足可能性判定問題3SATの正例題生成手法について
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- Dirichlet分布のrapidly mixing approximate sampler
- Dirichlet 分布の rapidly mixing approximate sampler
- パス幅を用いた#2SATの厳密アルゴリズム
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- MAX 2SATに対するシンプルな正解付テスト例題生成について
- Test Instance Generation for MAX 2SAT with Fixed Optimal Value (New Aspects of Theoretical Computer Science)