权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

組合せ論的計算量の理論-特に下界の証明と最適アルゴリズムの-意性の問題

组合复杂性理论 - 特别是下界和最优算法的证明 - 任意性问题

基本信息

批准号：
06780246
负责人：
垂井淳
金额：
$ 0.64万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至 1995
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780246/
关键词：
計算量ブール関数マージ比較器回路 ACC

项目摘要

本研究では、いくつかの組合せ論的計算モデルについて、計算能力の解析と“自然な"計算問題を解くのに必要な計算資源の量の分析を行なった。以下では、今年度論文としてまとめるに至ったものについてより詳しく述べる。1.constant-depth polynomial-sizeの組合せ論理回路によって定義される計算量のクラスACCについて、以前よりRichard Beigel(Yale大学)と共同研究を行なっていたが、今年度この結果をJ.of Comp.Complexityに発表した。この論文では、クラスACCに属する任意のブール関数は、深さ2のある形の回路で計算可能であること等が示されている。2.整列されている2つのリストをcomparator(比較器)によって併合するmergng networkに必要なcomparatorの数について、Batcherのodd-even mergeに基づくものが、漸近的に最適であるという結果を含む論文のjournal versionを今年度まとめた。これは、以前よりの共同研究を発展させたもので、論文は現在審査中である。

This study focuses on the analysis of computational power and the amount of computational resources necessary to solve the "natural" computational problem. The following is a detailed description of this year's paper. 1. The computational complexity of the constant-depth polynomial-size combination in logic circuits is defined by the complexity of ACC, previously conducted by Richard Beigel(University of Yale) and joint research, and this year's results were announced by J. of Comp. Complexity. This paper shows that the number of arbitrary connections between ACC and the number of deep connections between ACC and ACC is 2. 2. The number of comparators required for the whole array is 2, the number of comparators required for the mergg network is 2, the number of comparators required for the odd-even merge is 2, This paper is currently under review.