二分決定グラフの性質と並列処理アルゴリズムに関する研究

本研究では、論理設計支援の分野で論理関数の内部表現として広く利用されるなど、効率的な論理的関数の表現法として注目されている二分決定グラフについて、その論理関数の表現能力等理論的な立場からの研究をおこなった。1.共有二分決定グラフの性質に関する研究(1)変数割当とそれに対する論理関数値の組をいくつか与えたとき、それを満たす幅 k以下の二分決定グラフが存在するかという、二分決定グラフの最小推論問題がNP完全であることを示した。この結果から、二分決定グラフのPAC学習が不可能であることが導かれた。これは、不完全指定論理関数の二分決定グラフによる処理の複雑さを示したとも考えられる。(2)閾値関数を表す二分決定グラフのサイズについて考察し、任意の閾値関数を表現するのに必要なサイズの上界及び下界を示した。変数の順序を固定した場合、適切な変数順序を選べる場合ともに指数的な下界が得られた。特に前者の場合においては上界と定数まで一致し、必要な二分決定グラフノサイズが完全に明らかにできた。論理関数処理の計算複雑さに関する研究以前からおこなっていた二分決定グラフの並列処理アルゴリズムに関する研究を進め、この成果をまとめた。また、機能メモリ上での二分決定グラフ処理手法について検討をおこなった。

本研究では、論理設計支援の分野で論理関数の内部表現として広く利用されるなど、効率的な論理的関数の表現法として注目されている二分決定グラフについて、その論理関数の表現能力等理論的な立場からの研究をおこなった。1.共有二分決定グラフの性質に関する研究(1)変数割当とそれに対する論理関数値の組をいくつか与えたとき、それを満たす幅 k以下の二分決定グラフが存在するかという、二分決定グラフの最小推論問題がNP完全であることを示した。この結果から、二分決定グラフのPAC学習が不可能であることが導かれた。これは、不完全指定論理関数の二分決定グラフによる処理の複雑さを示したとも考えられる。(2)閾値関数を表す二分決定グラフのサイズについて考察し、任意の閾値関数を表現するのに必要なサイズの上界及び下界を示した。変数の順序を固定した場合、適切な変数順序を選べる場合ともに指数的な下界が得られた。特に前者の場合においては上界と定数まで一致し、必要な二分決定グラフノサイズが完全に明らかにできた。論理関数処理の計算複雑さに関する研究以前からおこなっていた二分決定グラフの並列処理アルゴリズムに関する研究を進め、この成果をまとめた。また、機能メモリ上での二分決定グラフ処理手法について検討をおこなった。