Lower Bounds in Computer Science

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

We focus our attention on finding lower bounds of the number M(m,n) of comparators in (m,n)-merging networks. M(n,n), (n < 5,n = 7,8,9) and 16 < oM(6,6) < 17 are already known. We proved that M(6,6) = 17. (The paper is published.)We derived a lower bound theorem concerning M(m,n), and showed that infinite-many Batcher's odd-even merge are optimal. By the theorem, we solved an open problem posed by Yao and Yao, which has been open for a quarter century. (The paper is published.)Consider Tsume-Shogi on n x n Shogi-board. We proved that the problem to determine whether the attack-side player (the first player) can give checkmate the game is EXPTIME complete. (The paper is published.)For a directed acyclic graph G with n nodes, T(G) is defined to be the number of the ways to assign integers 1,2, …, n to the nodes of G so that the number on node u is less than the one on v for an edge (u,v) in G. According to the definition, T(G] can be computed in O(n^2・n^!) steps. We presented an algorithm to compute T(G) in O(n^2 2^n) steps. (The paper is published in IEICE Technical Report.)As far as other researchers are concerned, Dr. Kasai showed a polynomial time inference algorithm, and a result in formal language. Dr. Takenaga gave some properties on ordered binary decision diagrams, and on tree-shellable boolean functions. Dr. Hasunuma showed properties on graph theory, and gave some graph algorithms. These results are considered as basic studies for our research project, and we will further develop these theories in our future research.