部分ゲートとその同定
スポンサーリンク
概要
- 論文の詳細を見る
部分ゲートとは、入力の一部に対する関数を計算するゲートである。与えられた部分ゲートに対して、どの入力が接続されているかを同定する問題を考える。まずはじめに部分0R、部分AND、部分Parityゲートを考える。接続されている入力の本数が与えられていない場合は、上界と下界が一致し、与えられている場合は、上界と下界が同じオーダーを持つことを示す。部分0Rと部分ANDゲートの上界は決定的アルゴリズムで与えられるが、部分Parityゲートの上界は、ラスベガスアルゴリズムで与えられる。次に部分Thresholdゲートを考える。これはしきい値もパラメタになるので、問題が複雑になる。入力の本数が与えられ、しかもそれが小さい場合は上界と下界は同じオーダーを持ち、それ以外の場合は、下界とlog nギャップがある上界が得られている。
- 社団法人電子情報通信学会の論文
- 1996-07-25
著者
-
上原 隆平
北陸先端科学技術大学院大学
-
土田 賢省
東洋大学工学部
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
東京女子大学情報処理センター
-
上原 隆平
東京女子大学
-
上原 隆平
東京女子大学情報処理教室
関連論文
- 直方体分割の24次格子グラフ表現とその応用 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 24分格子グラフによる直方体分割の描画
- 24分格子グラフによる直方体分割の描画
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- ネットワークニュースの自動編集システムにおけるキーワード検索の効率化
- 再構成問題の計算複雑さ
- 4L-4 組み込みソフト向けHichart開発環境における動作仕様検査(要求定義とプログラミング言語・設計・実装,学生セッション,ソフトウェア科学・工学)
- あみだくじの高速列挙
- 折紙の計算量的複雑さの研究 (小特集 折紙工学の現状と課題)
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- Polygons Folding to Plural Incongruent Orthogonal Boxes (Acceleration and Visualization of Computation for Enumeration Problems)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- じゃばら折りの複雑さに関する研究
- 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
- 複数の箱を折ることのできる展開図に関する研究
- 折り紙とコンピュータサイエンス(学生/教養のページ)
- コーダルグラフの完全列の列挙
- 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- スケールフリーグラフ上における局所情報を用いたランダムウォークについて
- 2部パーミュテーショングラフのバンド幅
- 航空路線問題に対する効率の良いアルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- プロープ区間グラフの拡張MPQ木表現
- 2部グラフとProbe区間グラフにおける木スパナー
- 2部グラフの部分クラスに対するGI完全性について
- 重み最大マッチングを求める並列近似アルゴリズム
- グラフの連結成分の個数と応用
- 弦グラフの一般化と、そのグラフ上での問題の難しさ
- ある投票ゲームのシミュレーション
- Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)
- 飛び出す絵本の複雑さ
- 単純多角形の生成に関する発見的手法(セッション2)
- グラフ上のボロノイゲームとその困難性(セッション1)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- ブロック線図文法(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- あるクラスの文脈依存グラフ文法とその性質 (計算モデルとアルゴリズム)
- 属性ブロック線図文法
- 負荷分散による並列シミュレーションのタイミングアルゴリズム
- Web カウンセリングシステムにおける描画検査
- オンラインカウンセリングシステムにおけるGUI
- D-7-6 オンラインカウンセリングシステムの構築(D-7. MEとバイオサイバネティックス,一般セッション)
- Syntactic Characterization of Two-Dimensional Grid Graphs by a Context-Sensitive Graph Grammar(New Trends in Theory of Computation and Algorithm)
- グラフ文法による図と表の処理の定式化
- 形式的文書操作のための表形式用XMLビューア
- Application of Attribute edNCE Graph Grammars to Syntactic Editing of Tabular Forms (New Developments of Theory of Computation and Algorithms)
- D-3-9 edNCEグラフ文法によるカルノー図型の表の作成
- 属性edNCEグラフ文法による表の構文的編集
- 3B-7 Octgridに基づく表編集アルゴリズム(アルゴリズムとその応用,一般セッション,ソフトウェア科学・工学)
- 2B-2 最急降下モデルによる日本全域尾根線つき3次元地形図の作成(数理モデル化と問題解決,一般セッション,ソフトウェア科学・工学)
- D-12-32 Octgridに基づく効率的な3D地形図生成法(D-12.パターン認識・メディア理解A(パターンメディアの認識・理解・生成),一般セッション)
- 表の格子グラフモデルと編集アルゴリズム
- 多層型矩形分割に対する16分格子グラフ表現 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- D-9-9 作業管理システムにおける携帯電話入力のコード化(D-9. オフィスインフォメーションシステム,一般セッション)
- D-3-3 組み込みソフトウェア向けHichart処理系の開発(D-3. ソフトウェアサイエンス,一般セッション)
- D-1-4 Octgridに対する属性グラフ文法による矩形数え上げ(D-1. コンピュテーション,一般セッション)
- A-6-13 24-ary Grid Graph Representation for the Rectangular Solid Dissections
- K-019 3D偏光立体視システムを利用した地理情報教材(K分野:教育工学・福祉工学・マルチメディア応用)
- A-003 8分格子モデルを用いた地形的特徴の認識システム(A分野:モデル・アルゴリズム・プログラミング)
- D-12-12 H7CODEに基づくVRML地形図エディタの開発(D-12.パターン認識・メディア理解,一般講演)
- D-9-3 携帯電話を用いた建設現場向け作業管理システム(D-9.オフィスインフォメーションシステム,一般講演)
- D-1-3 Octgridに対するパーザの開発(D-1.コンピュテーション,一般講演)
- D-1-2 スライス構造の表に対するグラフ文法(D-1.コンピュテーション,一般講演)
- 3D立体表示による地理・地学教育支援教材の応用可能性(教育におけるセキュリティ/一般)
- 帯状の紙の折りたたみに関する最適化問題
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- 一般化KaboozleのNP完全性
- 折紙における決定不能問題
- パス上のボロノイゲーム
- 帯状の紙の折りたたみに関する最適化問題
- 折紙における決定不能問題
- 一般化 Kaboozle のNP完全性
- プトレマイオスグラフのラミナー構造とその応用
- k-木のスケールフリー性に関する研究
- k-木のスケールフリー性に関する研究
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- Hoffmanパズル解の列挙と一般化に関する研究
- 複数の直方体を折れる共通の展開図に関する研究
- グラフクラスとアルゴリズム
- 複数の直方体を折れる共通の展開図に関する研究
- ゲーム・パズルの計算量を示すための新しい枠組みについて(パズルとゲームの計算理論)
- ある投票ゲームのシミュレーション