正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
スポンサーリンク
概要
- 論文の詳細を見る
文献[Bar89]において,Barringtonは,段数dの任意の論理回路が5次の交代群の上で動作する長さ4^dのモノイドプログラムによって模倣できることを示した.さらに,この結果の拡張として,任意の非可解群Gに対しても同様の結果が成り立つことを示している.ただし,このときのモノイドプログラムの長さは4^dではなく,(4|G|)^dになっている.本稿では,任意の非可解群についても5次の交代群の場合と全く同じ結果が成り立つことを述べる.さらに,群の「非ベキ零性」がモノイドプログラムの計算能力に関するある種の境界を示していることを述べる.
- 一般社団法人電子情報通信学会の論文
- 1997-05-30
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析