否定数限定論理回路におけるマージングの複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 否定数限定論理回路一使用できるNOTゲートの個数を制限した, 2人力ANDゲート, 2人力ORゲート, NOTゲートからなる組合せ論理回路一における論理関数の複雑さについて考える. (n,n)-マージング関数とは, あらかじめソートされた2つの長さnの0,1系列 x_1≦・・・≦x_n, y_1≦・・・≦y_nを入力とし, これを併合した長さ2nの列z_1≦・・・≦Z_<2π> を出力する関数である. 本稿では, 使用できるNOTゲートの個数をt=(log_2log_2n-a)個に制限したときの, (n,n)-マージング関数の複雑さがΘ(2^an)であることを示す.
- 1999-07-21
著者
-
丸岡 章
東北大学大学院情報科学研究科
-
天野 一幸
東北大学大学院情報科学研究科
-
天野 一幸
群馬大学工学研究科情報工学専攻
-
垂井 淳
電気通信大学情報通信工学科
-
垂井 淳
電気通信大学情報理工学研究科情報・通信工学専攻
-
垂井 淳
電気通信大学 情報理工学研究科 情報・通信工学専攻
-
垂井 淳
電気通信大学情報理工学研究科
関連論文
- 最簡な論理式でNPN同値類の代表のみを生成するアルゴリズム
- 発見科学の構想と展開(発見科学)
- リスク情報を用いたオンライン資源分配
- 充足割り当て数を最小化/最大化する単調DNF式について
- 可変マージ関数の否定数限定複雑さ (計算モデルとアルゴリズム)
- 連数限定入力に対する否定数限定ソーティング回路
- 直交F-ホーン式の学習アルゴリズム
- ブール関数のPTF表現の複雑さについて
- ホーン式とXOR-MDNF式との関係について
- 交代数限定単調項決定リストの学習可能性
- 単調DNF式の排他的論理和の学習可能性
- モノポリストゲームのゲーム長(手数)について
- [チュートリアル講演]最小値独立置換族に関する最近の成果
- 最小値独立置換族に関する最近の成果
- 有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成
- k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界
- 置換族とその独立性の解析
- 和集合のサイズの近似評価について
- アルゴリズムの非確率化と制限付き独立性
- 単項性判定のための論理関数に関する条件
- 集中討論:DeolalikarのP≠NP論文をめぐって
- オンラインオークション型資源配分問題(計算理論とアルゴリズムの新展開)
- シャノンスイッチングゲームにおけるペアリング戦略の複雑さについて
- DS-1-14 ランダム写像による非線形概念の学習の効率化に向けて(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- マージンを保存するランダム性を限定したプロジェクションとブール空間への埋め込み
- リスク情報を用いたオンライン資源分配
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 二次論理関数の単調回路計算量について
- 分割と併合に基づくブーステイング
- 二次論理関数の単調回路計算量について
- 分割と併合に基づくブースティング
- 最適なマージングネットワークについて
- 最適なマージングネットワークについて
- オンライン学習の学習曲線に関する研究
- 計算の複雑さと効率化の研究(フェロー受賞記念講演)
- 単調論理関数の性質判定アルゴリズムについて
- LA-5 決定ダイアグラムに基づくブースティング(A. アルゴリズム・基礎)
- 単調論理関数間の距離について
- ランダムプロジェクションによる次元圧縮
- 論理関数のフーリエスペクトルと非線形性の関係
- 決定森の族の計算能力
- 制限付集合に対する包除原理の性質と数え上げ問題への応用
- 決定木における補助ビット問題について
- CC(6)型回路と(MOD3-MOD2)回路における計算の複雑さについて
- オンライン予測 (計算学習理論の進展と応用可能性)
- 否定数限定論理回路におけるマージングの複雑さ
- 最適なマージングネットワークについて
- 否定素子数限定論理回路における単調論理関数の複雑さ (アルゴリズムと計算の理論)
- マージ関数とソート関数の否定数限定複雑さ
- 完全K分木型組織構造の多階層関係追加モデル
- 連数限定入力に対する否定数限定ソーティング回路
- 回路計算量の線形下界に対する計算機支援証明について
- 最簡な論理式だけを生成するアルゴリズム(セッション1)
- P vs. NP問題 : 解決へのはるかな道(理論計算機科学の最新動向)
- 単調O(log n)項DNF式の学習
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- あるノイズモデルにおけるブール関数学習について
- Predicting like the best pruning of a decision tree
- 近似法のサイズ限定モデル
- フェイステル変換を用いた近似的k-対ランダム置換族の構成
- kトニックな0/1列に対する線形サイズ対数深さの否定数限定インバータ
- サイズ限定モデルに基づく近似法による単調複雑さの下界
- ブール関数のsensitivity, block sensitivity, certificate complexity について
- ブール関数のフーリエ変換とその応用
- 単調論理回路計算量vs.論理回路計算量
- クリーク関数の否定数限定複雑さ
- 否定素子数限定論理回路における単調論理関数の複雑さ
- 論理関数の複雑さと近似演算(計算理論とその応用)
- 論理関数の複雑さと近似演算
- 論理関数の複雑さと近似演算
- MDL原理に基づいた決定木枝刈りアルゴリズムのシミュレーション
- 複数の予測戦略を統合する実時間予測アルゴリズム
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)
- 複数の予測戦略を統合する実時間予測アルゴリズム
- 情報獲得と近似学習
- 相互情報量に基づく学習モデル
- ブールドメイン上の関数に対するサンプリングの定理
- 決定木に基づいたオンライン学習アルゴリズム
- 計算の複雑さと証明の複雑さ : 基調講演 (証明論と複雑性)
- 「AIマップ : 機械学習から機械発見へ」へのコメントと回答
- 単調論理関数と擬似補関数に対する近似モデル(計算モデルと計算の複雑さに関する研究)
- 否定制約のもとでのクリーク関数の複雑さに対する指数関数の下界
- 単調論理関数と擬似補関数に対する近似モデル
- 非単調論理回路に対する Razborov の近似モデルの構造
- 制限付回路モデルに対するRazborovの近似法の適用
- k-限定独立性に基づいたDNFの近似アルゴリズム