一定数の充足解を持つCNF式に対する準指数時間アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• 本稿では、実行時間と充足解の総数との間にトレードオフを持つCNF式に対する効率的なアルゴリズムを示す。アルゴリズムでは、まず非充足解の総数を求めるinclusion-exclusion公式とその数の近似に基づいた充足性判定アルゴリズムを構成する。次にその判定アルゴリズムをサブルーチンとして、充足解を2^n/δ個持つn変数、m項のCNF式φに対して、2^O(√<m>log3/2mlogδ)時間で充足解を求めるアルゴリズムを構成する。特にm=o(n^<2-ε>)、δ=2^<n^ε>(0≤ε < 1)の場合に準指数時間のアルゴリズムとなる。

• 2002-01-23

著者

• 松浦 昭洋

  京都大学大学院 情報学研究科 通信情報システム専攻

関連論文

• A-25 k-CNF式に対するInclusion-Exclusion公式における非充足解数計算手法(離散アルゴリズム(2),A.アルゴリズム・基礎)
• 一定数の充足解を持つCNF式に対する準指数時間アルゴリズム
• 2^n-α個の決定性状態を要するn状態NFAの族について

スポンサーリンク