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

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

• 批准号: 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値入力を先頭から読んだ場合の値の反転数が十分小さな場合には,否定素子の個数を小さな数に抑えても,線形サイズでこれを実現する回路が構成可能であると結果などを得た.加えて,論理式モデルにおける表現サイズを半正定置計画問題に帰着する手法に対する詳細な解析や,ある種の木構造をもつ表現形式における最適な情報伝達経路の構成法に関する成果等も得られた.

本研究旨在开发一种推导逻辑函数复杂度下界的方法，这一直是计算机科学领域几十年来的一个难题。本研究获得的结果如下： 1.在表示中。逻辑函数的方法称为有序决策二叉树，它在表示基本运算乘法所需的大小方面优于先前已知的方法。此外，通过计算机实验，我们得到的结果强烈表明该上限是最佳的。 2.逻辑电路中表达的逻辑函数的大小满足称为二次形式的属性我们研究了使用单调逻辑电路的情况。逻辑函数模型。由此，我们获得了一些关于计算此类函数的电路尺寸和电路结构的知识。我们还阐明了一些组合特性，这些特性表征了在具有某些结构的电路中表示尺寸变大的函数。 3.在具有有限数量的否定元素的逻辑电路模型中，我们研究了反相电路的尺寸以及当某些限制时的排序。结果我们发现如果从头读取二进制输入，结果表明，如果和值的反转次数足够小，则即使负元件的数量保持较小，也可以构造一个以线性尺寸实现此目的的电路。此外，逻辑公式 A 详细说明分析了将模型中的表示大小缩减为半正则固定规划问题的方法，并获得了在某种类型的树结构表示格式中构造最优信息传输路径的结果。

项目成果

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

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

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