MAX-3SATの解の平均の解析
スポンサーリンク
概要
- 論文の詳細を見る
本論文ではNP完全問題の1つである3充足可能性問題3SATの最適化であるMAX-3SATをとりあげる.一様ランダムに生成されたn変数m項の3CNFを入力としたMAX-3SATの解の平均を解析し, この値がおよそm / 8-O(√<mn>)以上であることを示した.また, 実験的な解析も行い, 論理的に得られた値と比較を行った.
- 2000-07-18
著者
関連論文
- 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)