NewDevelopments of Discrete-System Algorithmics Based on Complexes

基于复形的离散系统算法的新进展

• 批准号: 10205204
• 负责人: IMAI Hiroshi
• 金额: $ 6.98万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205204/
• 关键词: simplicial complex; discrete system; invariant polynomials; Tutte polynomial; Binary Decision Diagram (BDD); Groebner bases; quantun information; マトロイド; Grobner基底; 計算幾何・計算代数; 最適化; 情報幾何; Voronoi図

Simplicial complexes arise in various discrete systems, such as graphs, networks, matroids, convex polytopes, triangulations, etc. There have been known discrete invariant polynomials featuring a given simplicial complex, such as network reliability, chromatic polynomial, invariants of statistical physics and knots/links. We have developed efficient algorithms to compute these invariant polynomials based on the Binary Decision Diagram (BDD), and have shown that moderate-size problems can be solved in practice. Since most of these computation problems are known to be #P-hard, this is a quite remarkable result. We have also presented algebraic approaches to these problems, based on the Groebner bases in computational algebra and also triangulations in computational geometry. This unified approach was analyzed from the viewpoint of combinatorial complexity. We have further investigated new search methods for combinatorial search, geometric and probabilistic proximity structures, full text database search algorithms, etc. Finally, quantum computing and quantum information theory are treated as a natural extension of probabilistic computation and classical information theory, and their discrete structures have been revealed. In so doing, quantum computation simulators have been implemented and used. Some submodularity property of the quantum entropy is also shown.

单纯复形出现在各种离散系统中，例如图、网络、拟阵、凸多面体、三角剖分等。已知具有给定单纯复形特征的离散不变多项式，例如网络可靠性、色多项式、统计物理不变量和结/链接。我们开发了基于二元决策图 (BDD) 的有效算法来计算这些不变多项式，并表明在实践中可以解决中等规模的问题。由于大多数计算问题都被认为是#P-hard，所以这是一个非常了不起的结果。我们还基于计算代数中的 Groebner 基础以及计算几何中的三角剖分提出了解决这些问题的代数方法。从组合复杂性的角度分析了这种统一方法。我们进一步研究了组合搜索、几何和概率邻近结构、全文数据库搜索算法等新的搜索方法。最后，量子计算和量子信息论被视为概率计算和经典信息论的自然延伸，它们的离散结构已经被揭示。在此过程中，量子计算模拟器已经被实现和使用。还显示了量子熵的一些子模性质。