Computer Computation to obtain Lower Bounds of Computational Complexity

点击翻译按钮获取中文摘要

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.