Computer Computation to obtain Lower Bounds of Computational Complexity

我们的注意力集中在寻找(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技术报告上。)就其他研究者的研究而言，葛西纪明博士考虑了一种分析自然语言的算法，并定义了“左右树”来进行语法分析。然后他介绍了一种新型的下压式换能器的概念，并展示了这种换能器的一些特性。山崎博士分析了图形算法。他证明了对于一类图的某些参数是固定的，图的同构问题在多项式时间内是可解的。这些结果被认为是我们项目的基础研究，我们将在未来的研究中进一步发展这些理论。

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.