近似法に基づく論理関数の複雑さの評価に関する研究

基于近似方法评价逻辑函数复杂度的研究

• 批准号: 11780182
• 负责人: 天野 一幸
• 金额: $ 1.34万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11780182/
• 关键词: 回路計算量; 近似法; 決定木; 剰余回路; 並列計算; 単調; 否定素子数限定回路

本研究は,与えられた論理関数を計算する最小の論理回路のサイズに対する下界を導出する手法を開発することを目標とするものである.本研究では特に,この問題に対する有望な手法として知られる近似法を,従来は単調論理回路,すなわち,論理和ゲートと論理積ゲートのみからなる論理回路に対してのみ適用可能であったものから,一般の論理回路モデルや,更には決定木モデルにおいても適用可能となるように拡張することに主眼をおき研究を行った.本年度の研究において得られた主な結果は以下のとおりである.1.ゲートの出力値が,そのゲートの入力の和のある定数剰余によってのみ定まる,いわゆる剰余回路モデルにおいて,任意のサイズの定数段剰余回路は,2段の等価な剰余回路に変換可能であることを代数的手法を用いて示した.また,その出力値が入力変数のうち値1をとるものの個数で定まる関数である対称関数について,これを計算する2段の剰余回路に対する必要条件を,フーリエ変換的手法を用いて示した.また,これら2つの結果と近似法を組み合わせて,対称関数を計算する剰余回路のサイズの下界を導いた.2.並列計算のモデルとして,近年盛んに研究が行われている併置決定木群を用いた計算量について解析を行った.種々の論理関数の近似度,すなわち,与えられた論理関数をある限定された関数クラスに属する関数のみを用いて近似する場合の,近似の度合いの限界値について解析することを通して,併置決定木群の計算量に関する未解決問題のいくつかに対する回答を与えた.

This study is to calculate the minimum logic loop and the minimum logic loop. This study is aimed at solving these problems by using approximate methods and adjusting logic circuits, logical sums and logical products. Logic circuits can be applied to general logic circuits, and even more, they can be applied to decision making. The results of this year's research are as follows: 1. The output value of the generator is equal to that of the input force and the sum of the input force is equal to that of the input force. The residual loop is equal to that of the input force and the sum of the input force is equal to that of the input force. For example, the number of inputs and the number of inputs are determined by the number of inputs and the number of inputs is determined by the number of inputs and the number of inputs. 2. Parallel computation is a new method for calculating the correlation coefficient. 2. Parallel computation is a new method for calculating the correlation coefficient. The degree of approximation of the logical relationship of a species is limited to the logical relationship of a species. In the case of approximation, the degree of approximation is limited to the value of a species.

项目成果

Kazuyuki Amano: "On the Negation-Limited Circuit Complexity of Merging"Lecture Notes in Computer Science. 1627. 204-209 (1999)

Kazuyuki Amano：“论合并的负限制电路复杂性”计算机科学讲义。

天野一幸: "モノポリストゲームのゲーム長(手数)について"電子情報通信学会 技術研究報告 -コンピュテーション-. 2000・11. 41-48 (2000)

天野一之：“关于垄断游戏的游戏长度（步数）”IEICE技术研究报告-计算- 41-48（2000）。

天野一幸: "決定不における補助ビット問題について"電子情報通信学会 技術研究報告 -コンピュテーション-. 2000・10. 57-64 (2000)

Kazuyuki Amano：“关于未定情况下的辅助位问题”IEICE技术研究报告-计算-2000・10.57-64（2000）。

天野一幸: "ブール関数のフーリエ変換とその応用"電子情報通信学会誌. 82巻12号. 1270-1272 (1999)

Kazuyuki Amano：“布尔函数的傅立叶变换及其应用”，电子信息通信工程师学会杂志，第 82 卷，第 12 期。1270-1272 (1999)。

Kazoyoki Amano: "On the Negation-Limited Circuit Complexity of Merging"Discrete Applied Mathematics. (発表予定). (2001)

Kazoyoki Amano：“论合并的负限制电路复杂性”离散应用数学（即将发表）。