論理関数の近似計算と厳密計算の困難さのギャップに関する研究

逻辑函数近似计算与精确计算难度差距研究

• 批准号: 15700003
• 负责人: 天野 一幸
• 金额: $ 1.28万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700003/
• 关键词: 論理関数; 計算量; 下界; 単調論理回路; しきい値回路; 比較交換器回路; 否定素子数限定論理回路; マージング; クリーク関数

本研究は,論理関数の計算における近似計算と厳密計算との間に生ずる困難さのギャップを解析することを通じて,論理関数の複雑さの下限導出が可能な汎用的手法を開発することを目的としたものである.これに対して本年度得られた主な成果は以下の通りである.1.しきい値素子を用いた回路において,非限定的な重みを持つ1層のしきい値回路を,多項式的重みを持つ2層のしきい値回路によって模倣する,従来知られる手法よりも効率の良い手法を発見した.また,加算,比較等の基本的かつ重要な演算が,小さいサイズの2層のしきい値論理回路で計算可能であることを明らかにした.2.単調論理回路における2次関数の複雑さに関して,これを単層回路により計算した場合に必要な積素子の個数と,複層回路により計算した場合に必要な積素子の個数に指数関数的なギャップが生じることを明らかにした.また,単層回路における最小回路のサイズと複層回路における最小回路のサイズが真に異なる単調論理関数が存在するか否かを問うた,単層予想と呼ばれる未解決問題に対して,複数の出力をもつ単調関数群に対してはこのようなものが存在することを明らかにし,部分的な解答を与えた.3.一様分布における単調論理関数の学習問題について,極限的組み合わせ論における重要な結果であるKruskal-Katonaの定理を応用することにより,従来知られるものより単純かつ効率的な学習アルゴリズムを与えた.また,論理関数の感受度を解析することにより,理論的な性能限界を達成することのできる学習アルゴリズム構成のために必要な条件を発見した.

In this paper, the approximate calculation of logical relations and the intermediate calculation of logical relations are discussed. This year's major achievements include the following: 1. The weight of a polynomial is 1. The weight of a polynomial is 1. The weight of a polynomial is 2. The weight of a polynomial is 1. The weight of a polynomial is 2. The weight of a polynomial is 2. The calculation of the logic circuit of the two-level is possible. The calculation of the logic circuit of the two-level is possible. The calculation of the logic circuit of the single-level is possible. The calculation of the logic circuit of the two-level is possible. The calculation of the logic circuit of the single-level is possible. The calculation of the two-level is possible. Multi-layer loop calculation is necessary for the number of product elements, the number of exponential relationships, and the number of outputs. The minimum loop in a single layer loop and the minimum loop in a multi-layer loop are true and different. The single tuning logic relationship exists. The single layer is expected to call. The unsolved problem exists. The multiple outputs are expected to be adjusted. The single tuning logic relationship exists. Part of the solution is to solve the problem of learning simple logical relations. 3. The important result is to use Kruskal-Katona's theorem to solve the problem of learning simple logical relations. The sensitivity analysis of logical relations shows that the theoretical performance limits are achieved and the necessary conditions for learning are found

项目成果

Kazuyuki Amano, Akira Maruoka: "On Optimal Merging Networks"Lecture Notes in Computer Science (Proc.of 28^<th> MFCS). 2747. 152-162 (2003)

Kazuyuki Amano、Akira Maruoka：“论最佳合并网络”计算机科学讲义（Proc.of 28^<th> MFCS）。

On Learning Monotone Boolean Functions under the Uniform Distribution

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

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

Better Simulation of Exponential Threshold Weights by Polynomial Weights

通过多项式权重更好地模拟指数阈值权重

• 发表时间: 2004
• 期刊: Electronic Colloquium on Computational Complexity 11
• 作者: Kazuyuki Amano;Kazuyuki Amano
• 通讯作者: Kazuyuki Amano

Kazuyuki Amano, Akira Maruoka: "On Learning Monotone Boolean Functions under the Uniform Distributions"Theoretical Computer Science. 発表予定. (2004)

Kazuyuki Amano、Akira Maruoka：“论学习均匀分布下的单调布尔函数”理论计算机科学（2004 年）。

Kazuyuki Amano, Akira Maruoka: "The Potential of the Approximation Method"SIAM Journal on Computing. 33(2). 433-447 (2004)

Kazuyuki Amano、Akira Maruoka：“近似方法的潜力”SIAM 计算杂志。