3-SAT問題の数値解析的解法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では3-SAT問題の数値解析的解法を提示する。アルゴリズムの概要は以下の通りである。1.CNF式を節毎に分解し、論理積X∧Yをxy,論理和X∨Yをx=y-xy,否定X^^-を1-xで書き換え、連立方程式を得る。2.上記のようにして得られた連立方程式の定義域を{0,1}からRに拡張する。3.この連立方程式はn変数m連立方程式であるが、これをn変数n連立方程式に変換する。4.上記のようにして得られた連立方程式をMoore-Penrose一般逆行列を用いて数値的に解く。5.一定回数内で収束すれば充足可能、収束しなければ充足不能とする。このアルゴリズムの計算量は条件つきで多項式時間である。
- 社団法人電子情報通信学会の論文
- 1993-11-26
著者
関連論文
- 論理回帰分析法による脳機能画像からの知識の発見
- 多重線形関数を用いたニューラルネットワークの構造分析
- 重回帰分析に基づいた帰納学習アルゴリズム
- スペクトル理論による情報フィルタ
- 回帰分析に基づいた帰納学習アルゴリズム
- 回帰分析を用いた概念クラスタリングアルゴリズム
- 身体化された心に(embodied mind)と言葉をつなぐもの
- 身体化人工知能
- メタファーに基づく人工知能
- データマイニングツールKINO
- エンジニアリング環境モデルに基づく協調設計支援システム
- 火力発電プラントエンジニアリング支援 : 信号展開と変更通知
- 火力プラントエンジニアリング支援システム : 概要
- 確率分布の直観主義論理による推論
- 情報論理学の提唱
- 数値データの論理的推論
- パターン処理の近似としての記号処理
- モデルに基づくプラント制御ロジック生成支援システム
- プランニングを用いた制御ソフトウェア仕様の視覚的設計方式
- 古典論理のすべての公理を満たす連続値論理関係について
- 第2回マシンインテリジェンスに関する国際ワークショップ(International Workshop on Machine Intelligence 1993)の報告
- 連続制御ソフトウェアの設計支援について
- 脳機能画像からのデータマイニングについて
- 3-SAT問題の数値解析的解法
- 記号主義とコネクショニズムの統合パラダイム
- ニューラルネットワークによる非単調推論
- fMRI画像からの論理回帰分析法による知識発見 (小特集 「発見科学」及び一般演題)
- パターンの論理的推論--知識獲得問題の新解決法
- 予測モデルからのルール抽出--データマイニングの必須技術
- データマイニングツールKINO
- 最尤法と無差別原理を用いた確率分布からの帰納学習
- デ-タマイニングツ-ル KINO
- 最尤法を用いたニューラルネットワークからの命題獲得
- ニューラルネットワークからの命題の抽出
- 株データからの命題獲得
- 推論ツールKINOの開発
- 多項式時間帰納学習アルゴリズム
- 論理の幾何的モデルに基づいたルールと事例の協調推論の枠組