近似法に基づく論理関数の複雑さの評価に関する研究

点击翻译按钮获取中文摘要

本研究は,与えられた論理関数を計算する最小の論理回路のサイズに対する下界を導出する手法を開発することを目標とするものである.本研究では特に,この問題に対する有望な手法として知られる近似法を,従来は単調論理回路,すなわち,論理和ゲートと論理積ゲートのみからなる論理回路に対してのみ適用可能であったものから,一般の論理回路モデルや,更には決定木モデルにおいても適用可能となるように拡張することに主眼をおき研究を行った.本年度の研究において得られた主な結果は以下のとおりである.1.ゲートの出力値が,そのゲートの入力の和のある定数剰余によってのみ定まる,いわゆる剰余回路モデルにおいて,任意のサイズの定数段剰余回路は,2段の等価な剰余回路に変換可能であることを代数的手法を用いて示した.また,その出力値が入力変数のうち値1をとるものの個数で定まる関数である対称関数について,これを計算する2段の剰余回路に対する必要条件を,フーリエ変換的手法を用いて示した.また,これら2つの結果と近似法を組み合わせて,対称関数を計算する剰余回路のサイズの下界を導いた.2.並列計算のモデルとして,近年盛んに研究が行われている併置決定木群を用いた計算量について解析を行った.種々の論理関数の近似度,すなわち,与えられた論理関数をある限定された関数クラスに属する関数のみを用いて近似する場合の,近似の度合いの限界値について解析することを通して,併置決定木群の計算量に関する未解決問題のいくつかに対する回答を与えた.