充足可能性問題の新解法について
スポンサーリンク
概要
- 論文の詳細を見る
充足可能性問題(SAT)は基本的な問題であり,3-SATがNP完全問題であることや,Horn-SATが線形時間で解けることがよく知られている。:推論に於いてはHorn節は各エキスパート・システム等に用いられているが,記述能力が劣り,より一般での枠組でのアルゴリズムの開発が強く望まれている.そこで最近ではLP解法の進歩に伴って,分枝限定法,切除平面法等,数量的な方法が着目されてしいる。本稿ではSATの新しいアルゴリズムを提案し,その振舞いや今後の方向性について言及する。
- 1991-02-25