論理回路の出力パターン数え上げ(一般)
スポンサーリンク
概要
- 論文の詳細を見る
s個の論理素子g_1,g_2,...,g_sからなる論理回路をCとする.この時,入力x∈{0,1}^nに対するCの出力パターンを,(g_1(x),g_2(x),...,g_s(x))∈{0,1}^sなる長さsのベクトルと定義する.但し,1≦i≦sなるiについて,g_i(x)はxに対する素子g_iの出力とする.ここで,任意の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木を全彩色する多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 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.アルゴリズム・基礎)
- 剰余関数を計算するエネルギー複雑度の小さいしきい値回路
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 部分κ-木の一般化点ランキング
- 木の一般化辺ランキング
- 木の分割問題を解くアルゴリズム
- 直並列グラフの重み付き彩色の効率のよいアルゴリズム
- 部分k木で独立全域木を見つけるアルゴリズム
- 部分κ木に対する辺素な道問題のNP-完全性
- 部分k-木をf-辺彩色するアルゴリズム
- グラフの辺彩色及びƒ-辺彩色アルゴリズム
- 木,カクタスにおける点被覆の遷移可能性
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 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)ラベリングの遷移可能性(一般)
- 論理回路の出力パターン数え上げ(一般)