論理回路の出力パターン数え上げ
スポンサーリンク
概要
- 論文の詳細を見る
s個の論理素子g1,g2,...,gsからなる論理回路をCとする.この時,入力x∈{0,1}nに対するCの出力パターンを,(g1(x),g2(x),...,gs(x))∈{0,1}sなる長さsのベクトルと定義する.但し,1<=i<=sなるiについて,gi(x)はxに対する素子giの出力とする.ここで,任意の2入力ブール関数f:{0,1}2→{0,1}について,回路を構成する素子の全てが関数fを計算する論理回路をf-回路と定義する.本論文では,入力としてf-回路C が与えられた時に,Cの出力パターンを数え上げる問題に着目し,その計算複雑さの解析を行った.その結果,この問題がfによって,多項式時間で計算可能となるか,又は#P完全のいずれかになることを明らかにした.即ち,fに関する二分定理を得た.
- 2013-05-10
著者
-
周 暁
東北大学大学院情報科学研究科
-
内沢 啓
東北大学大学院情報科学研究科
-
内澤 啓
農林水産省構造改善局計画部資源課
-
内澤 啓
東北大学大学院情報科学研究科
-
森住 大樹
島根大学大学院総合理工学研究科
-
内澤 啓
山形大学大学院理工学研究科
-
王 征泓
東北大学大学院情報科学研究科
関連論文
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 需要点と供給点があるグラフの分割問題の近似可能性
- 直並列グラフの折れ曲がり最小の直交描画
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 需要と供給の木の分割
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- 部分k-木で辺素な道をみつけるアルゴリズム
- 部分k木を全彩色する多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 農業における自然エネルギの利用
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)
- エネルギー計算量に制限のある定数段しきい値論理回路のサイズの指数下界について
- An Energy Complexity Measure for Threshold Circuits that is Motivated by Biological Data on Cortical Computations (Theoretical Computer Science and its Applications)
- しきい値論理回路のエネルギー計算量
- しきい値論理回路のエネルギー計算量
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- グラフの距離辺彩色アルゴリズム
- 部分k木で辺素な道を見つけるアルゴリズム
- 木を辺ランク付けする効率のよいアルゴリズム
- 部分k木を[g,f]-辺彩色する多項式時間アルゴリズム
- 部分k-木に対する[g,f]-辺彩色アルゴリズム
- 部分κ木を辺彩色する並列アルゴリズム
- 部分$k$木を全彩色する線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- エネルギー複雑度を用いた線形決定木の下界導出
- LA-11 直並列グラフをリスト辺彩色するアルゴリズム(A. アルゴリズム・基礎)
- 直並列グラフをリスト辺彩色するアルゴリズム
- 部分k-木のl-点彩色多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- A-37 直並列グラフのリスト全彩色(グラフアルゴリズム(1),A.アルゴリズム・基礎)
- Lower bounds for linear decision trees via an energy complexity argument (コンピュテーション)
- 剰余関数を計算するエネルギー複雑度の小さいしきい値回路
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 部分κ-木の一般化点ランキング
- 木の一般化辺ランキング
- 木の分割問題を解くアルゴリズム
- 直並列グラフの重み付き彩色の効率のよいアルゴリズム
- 部分k木で独立全域木を見つけるアルゴリズム
- 部分κ木に対する辺素な道問題のNP-完全性
- 部分k-木をf-辺彩色するアルゴリズム
- グラフの辺彩色及びƒ-辺彩色アルゴリズム
- エネルギー複雑度を用いた線形決定木の下界導出
- 木,カクタスにおける点被覆の遷移可能性
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- グラフ上の拡散競争ゲームの計算複雑さ
- 論理回路の出力パターン数え上げ
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 関数$P^n_D$を計算するしきい値回路 (理論計算機科学の新展開)
- Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)
- 4.しきい値回路がひらく計算限界解明への道(計算限界の解明への多面的アプローチ-P vs NPに向けた最前線-)
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 論理回路の出力パターン数え上げ(一般)