SATの多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文ではSATの多項式時間アルゴリズムを提示する。基本的な考えは、以下の通りである。CNFを線形不等式の集合で表現し、値を{O,1}から[0,1]に拡張することで、多面体を得るが、この多面体には充足可能性と関係のない領域が存在する。その領域をある種の線形不等式で切除してゆく。充足不能のときには空になリ、充足可能のときには空にならない。本アルゴリズムは多項式時間アルゴリズムである。よって、P=NPが証明されたことになる。
- 社団法人電子情報通信学会の論文
- 2003-05-16
著者
関連論文
- 数値データからの帰納学習 : 論理関数による重回帰分析
- 脳機能画像のノンパラメトリック回帰分析
- 論理回帰分析法による脳機能画像からの知識の発見
- 多重線形関数を用いたニューラルネットワークの構造分析
- 重回帰分析に基づいた帰納学習アルゴリズム
- 回帰分析に基づいた帰納学習アルゴリズム
- 回帰分析を用いた概念クラスタリングアルゴリズム
- 身体化された心に(embodied mind)と言葉をつなぐもの
- 身体化人工知能
- メタファーに基づく人工知能
- データマイニングツールKINO
- エンジニアリング環境モデルに基づく協調設計支援システム
- スペクトル理論を用いた学習アルゴリズムについて
- 数値データからの論理命題の発見
- 火力発電プラントエンジニアリング支援 : 信号展開と変更通知
- 数値データからの論理命題の発見
- 制御用ソフトウェアの生産技術 フィードバック制御
- 火力プラントエンジニアリング支援システム : 概要
- 不確実な知識を表現する非古典論理のモデル
- 確率分布の直観主義論理による推論
- 確率データからの帰納学習
- プリント配線板における部品配置エキスパートシステム
- 命題論理の幾何的モデル
- ロボットにことばをしゃべらせるには--身体化人工知能 (小特集 20世紀の人工知能を振り返って(21世紀の人工知能の展望))
- 記号主義とコネクショニズムの統合パラダイム
- F-038 生物学的手法によるニューラルネットワークの進化・学習 : 生物の感情獲得シミュレーション(F分野:人工知能・ゲーム)
- 株式の予測について : 初心者のための解説
- 感情の作り方(ニューラルネットワークの場合) (シンポジウム:情念について)
- 身体運動意味論
- 身体運動意味論の展開(1)実験認知言語学の予備的実験
- 身体運動意味論--言語・イメージ・身体 (特集 脳科学の最前線)
- 論理回帰分析法によるfMRI画像の解析(福祉・医療のためのパターン認識・メディア理解)
- 論理回帰分析法によるfMRI画像の解析(福祉・医療のためのパターン認識・メディア理解)
- 論理回帰分析法によるfMRI画像の解析(福祉・医療のためのパターン認識・メディア理解)
- 身体運動意味論--実験認知言語学へ向けて
- SATの多項式時間アルゴリズム
- 「ニューロラルな視点からの挑戦」へのコメントと回答
- ニューラルネットワークによる非単調推論
- fMRI画像からの論理回帰分析法による知識発見 (小特集 「発見科学」及び一般演題)
- パターンの論理的推論--知識獲得問題の新解決法
- 予測モデルからのルール抽出--データマイニングの必須技術
- データマイニングツールKINO
- 最尤法と無差別原理を用いた確率分布からの帰納学習
- デ-タマイニングツ-ル KINO
- 最尤法を用いたニューラルネットワークからの命題獲得
- ニューラルネットワークからの命題の抽出
- 株データからの命題獲得
- 推論ツールKINOの開発
- 多項式時間帰納学習アルゴリズム
- 論理の幾何的モデルに基づいたルールと事例の協調推論の枠組
- 身体運動意味論と身体運動統語論 (第10回日本認知言語学会シンポジウム)
- 脳機能画像のノンパラメトリック回帰分析 (MEとバイオサイバネティックス)
- 日本語と英語の間主観性の差に関する身体運動意味論的考察(主観性とパースペクティブ)
- 脳機能画像のノンパラメトリック回帰分析
- ノンパラメトリック線形回帰分析を用いた脳の賦活領域の検出(生体工学)