NewDevelopments of Discrete-System Algorithmics Based on Complexes

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

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.