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

Lower Bounds in Computer Science

计算机科学的下限

基本信息

批准号：
10680342
负责人：
IWATA Shigeki
金额：
$ 1.34万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2001
项目状态：
已结题

项目摘要

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.

我们把注意力集中在寻找（m，n）-合并网络中比较器个数M（m，n）的下界上。M（n，n），（n < 5，n = 7，8，9）和16 < oM（6，6）< 17是已知的。我们证明了M（6，6）= 17。(The论文发表）。我们导出了关于M（m，n）的一个下界定理，并证明了无限多个Batcher的奇偶归并是最优的。利用这个定理，我们解决了姚和姚提出的一个公开问题，这个问题已经公开了四分之一世纪。(The论文发表）。考虑在n × n将棋棋盘上的常将棋。我们证明了确定攻击方玩家（第一个玩家）是否可以将死游戏的问题是EXPTIME完成的。(The论文发表）。对于n个结点的有向无圈图G，T（G）被定义为G中任意一条边（u，v）的整数1，2，.，n分配给G中结点的方式的个数，使得结点u上的个数小于v上的个数.在O（n^2·n^！）的情况下，算法的时间复杂度是O（n^2·n^！步我们给出了一个计算T（G）的算法，时间复杂度为O（n^22^n）. (The论文发表在IEICE技术报告中。就其他研究人员而言，加塞博士展示了一个多项式时间推理算法，并以形式语言给出了一个结果。Takenaga博士给出了有序二元决策图和可树壳布尔函数的一些性质。莲沼博士展示了图论的性质，并给出了一些图形算法。这些结果被认为是我们研究项目的基础研究，我们将在未来的研究中进一步发展这些理论。