近似法による計算の複雑さの評価に関する研究

本研究は,与えられた論理関数を計算する最小サイズの論理回路のサイズの下界を導出する新たな手法を開発することを目標とするものである.本研究では特に,この問題に対する有望な手法として知られる近似法を,従来は単調論理回路,すなわち論理和ゲートと論理積ゲートのみからなり否定ゲートの使用を許さない論理回路に対してのみ適用可能であったものから,一般の論理回路モデルにおいても適用可能となるように拡張することに主眼をおき研究を行った.本研究により得られた主な結果は以下の通りである.1. 単調論理回路と一般の論理回路の中間的なモデルにあたる,否定素子数限定論理回路,すなわち使用できる否定ゲートの個数を制限した論理回路にまで適用可能となるような,近似法に対する拡張を得た.また,この手法を用いて,入力として与えられたm頂点無向グラフにサイズがm/2の完全グラフが含まれるか否かを判定する論理関数であるm頂点m/2クリーク関数は,否定ゲートの使用を(1/6)log log m個以下に制限すると,多項式サイズの論理回路では計算できないことを証明した.2. 従来単調回路に対してのみ適用可能であった,近似法とは異なる符号理論的論法を用いた下界導出手法についても,否定素子数限定論理回路モデルにまで適用可能であることを明らかにした.また,この手法を用いて,2つのソート済みのn変数の組をマージする関数を計算する最適な回路を求める問題に対し,使用できる否定ゲートの個数が0個からn個の全ての場合に対して,最適な回路のサイズの高々定数倍のサイズを持つ論理回路の構成法を与えた.

本研究は,与えられた論理関数を計算する最小サイズの論理回路のサイズの下界を導出する新たな手法を開発することを目標とするものである.本研究では特に,この問題に対する有望な手法として知られる近似法を,従来は単調論理回路,すなわち論理和ゲートと論理積ゲートのみからなり否定ゲートの使用を許さない論理回路に対してのみ適用可能であったものから,一般の論理回路モデルにおいても適用可能となるように拡張することに主眼をおき研究を行った.本研究により得られた主な結果は以下の通りである.1. 単調論理回路と一般の論理回路の中間的なモデルにあたる,否定素子数限定論理回路,すなわち使用できる否定ゲートの個数を制限した論理回路にまで適用可能となるような,近似法に対する拡張を得た.また,この手法を用いて,入力として与えられたm頂点無向グラフにサイズがm/2の完全グラフが含まれるか否かを判定する論理関数であるm頂点m/2クリーク関数は,否定ゲートの使用を(1/6)log log m個以下に制限すると,多項式サイズの論理回路では計算できないことを証明した.2. 従来単調回路に対してのみ適用可能であった,近似法とは異なる符号理論的論法を用いた下界導出手法についても,否定素子数限定論理回路モデルにまで適用可能であることを明らかにした.また,この手法を用いて,2つのソート済みのn変数の組をマージする関数を計算する最適な回路を求める問題に対し,使用できる否定ゲートの個数が0個からn個の全ての場合に対して,最適な回路のサイズの高々定数倍のサイズを持つ論理回路の構成法を与えた.