Computer Computation to obtain Lower Bounds of Computational Complexity

计算机计算以获得计算复杂性的下限

• 批准号: 07680345
• 负责人: IWATA Shigeki
• 金额: $ 1.47万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07680345/
• 关键词: Complxity; Lower Bound; Computation; Computers; Merging Network

We focus our attention on finding lower bounds of the number M (m, n) of comparators in (m, n) -merging networks. M (1, n) is obvious, and M (2, n), M (3, n) are known. M (n, n), n<less than or equal>5, n=7,8,9 have already been obt1. Concerning M (6,6), 16<less than or equal>M (6,6) <less than or equal>17 is known. We proved that M (6,6) =17. (The paper is under2. We proved that M (4,5) =12, M (4,6) =14, and that M (4,8) =18. The proof of M (4,5) =14 contains enormous computations by Workstation. IN the computation, we have constructed all merging networks having 13 comparators, and have examined that those constructed networks are not (4,6) -merging networks. Particular considerations on programs, such as backtracking and data structures were necesssary to reduce the amount of computation time. (The paper is already published.)3. By computer computation, we obtained that M (4,7) = 16, and that M (5,6) =16. We had to invent methods to make the computation time short, which include distributed computing. (The paper is published in IEICE Technical Report.)As far as researches of the other investigators are concerned, Dr.Kasai considered an algorithm to analyze natural languages, and defined "left-right tree" for the syntax analysis. He then introduced the notion of a new type of a pushdown transducer, and showed some properties of the tranducer. Dr.Yamazaki analyzed graph algorithms. He proved that the graph isomorphism problem is solvable in polynomial time for a class of restricted graphs where some parameters of the graphs are fixed. These results are considered as basic studies for our project, and we will further develop these theories in our future research.

我们的注意力集中在寻找(m，n)-合并网络中比较器数目M(m，n)的下界。M(1，n)是明显的，M(2，n)，M(3，n)是已知的。M(n，n)，n；小于或等于&gt；5，n=7，8，9已经是obt1。关于M(6，6)，16小于或等于&gt；M(6，6)&lt；小于或等于&gt；17是已知的。证明了M(6，6)=17。证明了M(4，5)=12，M(4，6)=14，M(4，8)=18。M(4，5)=14的证明包含大量的计算量。在计算中，我们构造了具有13个比较器的所有合并网络，并检验了所构造的网络不是(4，6)-合并网络。有必要对程序进行特别考虑，如回溯和数据结构，以减少计算时间。通过计算机计算，我们得到了M(4，7)=16，M(5，6)=16。我们必须发明一些方法来缩短计算时间，其中包括分布式计算。(这篇论文发表在IEICE技术报告上。)就其他研究者的研究而言，葛西纪明博士考虑了一种分析自然语言的算法，并定义了“左右树”来进行语法分析。然后他介绍了一种新型的下压式换能器的概念，并展示了这种换能器的一些特性。山崎博士分析了图形算法。他证明了对于一类图的某些参数是固定的，图的同构问题在多项式时间内是可解的。这些结果被认为是我们项目的基础研究，我们将在未来的研究中进一步发展这些理论。

项目成果

藤芳明生: "多段階木変換機について" 京都大学数理科学講究録. (掲載予定).

藤吉昭夫：《关于多级树变换器》京都大学数学科学讲座记录（待出版）。

Akio Fujiyoshi and Takumi Kasai: "Multi-phaze tree transformations" IEICE Trans. Fundamentals. E80-A. 761-768 (1997)

Akio Fujiyoshi 和 Takumi Kasai：“多相树变换”IEICE Trans。

Kazuhisa Masuda and Shigeki Iwata: "Some lower bounds of merging networks" The Trans.of the IEICE D-1. J80-D-I. 665-673 (1997)

Kazuhisa Masuda 和 Shigeki Iwata：“合并网络的一些下限”IEICE D-1 的 Trans.。

Koichi Yamazaki, Hans L.Bodlaender, Babette de Fluiter, and Dimitrios M.Thilikos: "Isomorphism for graphs of bounded distance widths" Lecture Notes in Comput.Sci.1203 Algorithms and Complexity (ed.Giancarlo Bongiovanni et al.). 276-287 (1997)

Koichi Yamazaki、Hans L.Bodlaender、Babette de Fluiter 和 Dimitrios M.Thilikos：Comput.Sci.1203 算法和复杂性中的“有界距离宽度图的同构”讲义（ed.Giancarlo Bongiovanni 等人）。

水野響: "マージングネットワークにおける.ある下界について" 京都大学数理科学講究録. (掲載予定).

Hibiki Mizuno：“关于合并网络中的某个下界”京都大学数学科学讲师（待出版）。