NewDevelopments of Discrete-System Algorithmics Based on Complexes

简单复合体出现在各种离散系统中，如图、网络、拟阵、凸多面体、三角剖分等。已知的离散不变多项式具有给定的简单复合体，如网络可靠性、色多项式、统计物理的不变量和结点/链接。我们开发了基于二进制决策图（BDD）的有效算法来计算这些不变多项式，并证明了在实践中可以解决中等规模的问题。由于已知这些计算问题中的大多数都是#P-hard，因此这是一个相当了不起的结果。我们也提出了这些问题的代数方法，基于计算代数中的格罗布纳基和计算几何中的三角剖分。从组合复杂性的角度对这种统一方法进行了分析。我们进一步研究了组合搜索、几何和概率接近结构、全文数据库搜索算法等新的搜索方法。最后，将量子计算和量子信息理论视为概率计算和经典信息理论的自然延伸，揭示了它们的离散结构。在这样做，量子计算模拟器已经实现和使用。量子熵的一些亚模性也得到了证明。

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.