無矛盾最小OBDD問題の近似困難性について
スポンサーリンク
概要
- 論文の詳細を見る
順序付き二分決定グラフ(OBDD)は, 論理関数の有向グラフによる効果的な表現である. 無矛盾最小OBDD問題とは, ある論理関数について与えられた不完全な真偽値表から, その表に無矛盾かつ最小のOBDDを求める問題である. 本稿では, 任意に固定された変数順序について, この問題が計算量的に困難なことを示す. また, P≠NPの仮定の下では, n変数のとき常に最小サイズのn^ε倍以下のOBDDを出力するような多項式時間近似アルゴリズムがこの問題に対して存在しない, そのような定数ε>0があることを示す.
- 社団法人電子情報通信学会の論文
- 1996-05-17
著者
-
平田 耕一
九州工業大学情報工学研究院
-
篠原 歩
九州大学理学部基礎情報学研究施設
-
下薗 真一
九州工業大学知能情報工学科
-
下園 真一
九州工業大学情報工学部制御システム工学科
-
篠原 歩
九大 大学院システム情報科学研究院
-
平田 耕一
九州工業大学
関連論文
- 人工知能基本問題研究会(SIG-FPAI)(研究会総覧)
- 九州大学における一般情報処理教育支援システムについて
- 帰納的実数値関数の帰納推論における論駁性と信頼性(アルゴリズム一般)
- 帰納的実数値関数の帰納推論における論駁性と信頼性
- ラベル無し順序木のqグラム距離
- 質問学習における学習可能性の統一的特徴づけ
- Learning pattern languages using queries
- Learnability of Subsequence Languages
- 順序付き二分法定グラフの学習可能性
- 反駁PAC学習可能性
- 類推機能をもった対話型シークェント計算証明システムの開発(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 並列知識獲得システムBONSAI Garden
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 薬剤取り違え防止のための医薬品名類似性指標 (特集 「医療及び化学情報マイニング」および一般)
- 1変数文字列方程式の最小解の長さの上限
- 圧縮されたテキスト上のパターン照合 : データ圧縮とパターン照合の新展開
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 平衡直線的プログラムに対するパターン照合アルゴリズム
- 2G-2 圧縮テキストに対する文字列照合のための統一的枠組み
- 2G-1 データ圧縮による文字列照合の高速化
- 文字列パターン照合のための損失のあるデータ圧縮
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
- 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
- 直列エピソードから構成可能なエピソードのグラフ理論的性質 (特集 「ウェブマイニング」および一般)
- 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
- 人間指向型汎用類推証明システムの開発 (計算機科学基礎理論の新展開)
- 類推機能をもった対話型シークェント計算証明システムの開発 (計算機科学基礎理論の新展開)
- Pre-Checkingに基づく効率的スキーママッチングアルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- Pre-checkingを用いた効率的2階述語マッチングアルゴリズム (計算理論とアルゴリズムの新展開)
- スキーママッチングを用いたLK類推証明システムの開発
- スキーママッチングとその計算量
- スキーママッチングにおける計算の複雑さ (計算モデルとアルゴリズム)
- スキーママッチングの計算の複雑さ
- 古典的証明に基づく関数型言語の構築
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- ALT'96報告
- K語近接相関パタンの高速発見アルゴリズム
- On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
- 文字列相関パタンの分類精度最大化問題について
- DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- Minimum Multiset Covering 問題の近似アルゴリズムについて
- 平面巡回セールスマン問題の高速な近似アルゴリズム
- 無矛盾最小OBDD問題の近似困難性について
- ゲノムデータベース(5)配列データからの知識発見
- LZW圧縮テキストに対する高速文字列照合アルゴリズム
- コンピュ-タの推論による知識発見の支援(情報) (ゲノムサイエンス--生命の全体像の解明をめざして) -- (第1部 日本におけるヒト・ゲノム研究の最前線)
- 短縮記述された文字列上での多項式時間照合アルゴリズム
- ALT '94報告
- 生体分子ネットワークレイアウトのための2次元近似照合によるハイブリッドレイアウトアルゴリズム
- 石灰石球の熱分解における熱移動と CO_2 ガスの流れ
- 32 石灰石球の熱分解における熱及び物質の移動(製銑基礎・コークス, 製銑, 日本鉄鋼協会第 84 回(秋季)講演大会)
- 一階論理式の学習と帰納論理プログラミング (計算学習理論の進展と応用可能性)
- 決定可能な高階単一化問題に関する研究 (アルゴリズムと計算の理論)
- 単純型付きラムダ計算における証明文法
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 型付ラムダ計算における証明文法
- 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
- 木編集距離の研究動向(編集委員今年の抱負2013)
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)