論理関数の複雑さの下限導出問題に対する極限組み合わせ論的アプローチ

逻辑函数复杂度下界求导问题的极限组合方法

• 批准号: 17700001
• 负责人: 天野 一幸
• 金额: $ 1.34万
• 依托单位: Gunma University (2006)Tohoku University (2005)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700001/
• 关键词: 計算量理論; 論理関数; 論理回路; 計算複雑さ; 下界; 複雑さ; 線形計画法; 二分決定グラフ

本研究は,計算機科学分野において数十年来の難問とされている,論理関数の複雑さの下限を導出する手法の開発を目指したものである.本研究により得られた結果は以下の通りである.1.順序付決定二分木と呼ばれる論理関数の表現手法において,基本的演算である乗算を表する際に必要となるサイズに関して,従来知られるものより,優れた上界を得た.また,計算機実験によって,この上限が最適であることを強く示唆する結果を得た.2.論理関数を論理回路で表現する際のサイズについて,2次形式と呼ばれる性質を満たす論理関数に対する単調論理回路モデルを用いたケースに関して検討を行った.この結果,この種の関数を計算する回路サイズと回路構造に関するいくつかの知見が得られた.また,ある種の構造を持つ回路において表現サイズが大きくなるような関数を特徴付ける,幾つかの組み合わせ論的性質を明らかにした.3.否定素子の使用個数を限定した論理回路モデルにおいて,入力にある種の制限を設けた場合のソーティングあるいは,反転回路のサイズに関する検討を行った.その結果,2値入力を先頭から読んだ場合の値の反転数が十分小さな場合には,否定素子の個数を小さな数に抑えても,線形サイズでこれを実現する回路が構成可能であると結果などを得た.加えて,論理式モデルにおける表現サイズを半正定置計画問題に帰着する手法に対する詳細な解析や,ある種の木構造をもつ表現形式における最適な情報伝達経路の構成法に関する成果等も得られた.

This study provides an insight into the development of methods for deriving the lower bound of complex logic relations, which has been a difficult problem for decades in the field of computer science. The results of this study are as follows: 1. The expression of logical relations in order to determine the binary tree is necessary for the calculation of the binary tree, and the optimal upper bound is obtained. 2. Logic relations, logic loops, performance relations, second order forms, properties, logic relations, logic loops, performance relations. As a result, the relationship between the species and the loop structure is calculated. 3. Limit the number of negative elements used in logic circuits. 3. Limit the number of negative elements used in logic circuits. 4. Limit the number of negative elements used in logic circuits. 5. Limit the number of negative elements used in logic circuits. The result is that the number of negative elements is very small, and the number of negative elements is very small. Add to this, logic expression, expression, semi-definite design problem, technique, detailed analysis, tree structure, expression, optimal information, path construction, achievement, etc.

项目成果

On the Complexity of Depth-2 Circuits with Threshold Gates

关于具有阈值门的深度 2 电路的复杂性

• 发表时间: 2005
• 期刊: Lecture Notes in Computer Science 3618
• 作者: Kei Uchizawa;Kazuyuki Amano;Hideaki Fukuhara;澤田 清;瀧本 英二;Shigeaki Harada;Shigeaki Harada;酒井 義文;天野 一幸;Kazuyuki Amano;Takayuki Sato;内沢 啓;Kazuyuki Amano;Shigeaki Harada;Tatsuya Watanabe;酒井義文;Nobuyoshi Sato;Kazuyuki Amano;Kazuyuki Amano
• 通讯作者: Kazuyuki Amano

Better upper bounds on the QOBDD size of integer multiplication

整数乘法 QOBDD 大小的更好上限

• 发表时间: 2007
• 期刊: Discrete Applied Mathematics 155(10)
• 作者: Kei Uchizawa;Kazuyuki Amano
• 通讯作者: Kazuyuki Amano

On Learning Monotone Boolean Functions under the Uniform Distribution

均匀分布下单调布尔函数的学习

• 发表时间: 2005
• 期刊: Theoretical Computer Science (発表予定)
• 作者: Kazuyuki Amano

Tighter Bounds on the OBDD Size of Integer Multiplication

整数乘法 OBDD 大小的更严格限制

• 发表时间: 2005
• 期刊: Proc.of 4th Japanese-Hungarian Symp.on Disc.Math.and its Applications
• 作者: Kazuyuki Amano;Akira Maruoka
• 通讯作者: Akira Maruoka

On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences

关于k-tonic序列排序和反转的负限制电路复杂度

• 发表时间: 2006
• 期刊: Lecture Notes in Computer Science 4112
• 作者: Kei Uchizawa;Kazuyuki Amano;Hideaki Fukuhara;澤田 清;瀧本 英二;Shigeaki Harada;Shigeaki Harada;酒井 義文;天野 一幸;Kazuyuki Amano;Takayuki Sato
• 通讯作者: Takayuki Sato