Computing Partition Functions in Hard Problems of Combinatorial Enumeration and Optimization

组合优化问题关注的是找到一个函数的最优值，这个函数定义在一个有限的，虽然很大的集合上。这样的问题在现实世界中有很多应用，而且在大多数情况下，众所周知很难解决，因为可能的解决方案的集合太大了。P.I.打算通过配分函数的方法来研究这些问题，这种方法在很大程度上受到统计物理学的启发。这将为以前难以解决的问题带来新的高效算法。该项目解决的特殊问题包括与（超）图中完美匹配相关的配分函数的有效计算，图中的哈密顿循环和团，图同态，以及多元实数二次方程系统。它将使人们能够识别出可有效解决的难题。例如，人们将能够有效地区分具有足够多（但仍然很难找到）哈密顿循环的图和距离哈密顿循环足够远的图。

Problems of combinatorial optimization concern finding the optimal value of a function defined on a finite, though very large, set. Such problems have many real world applications and, for the most part, are notoriously difficult to solve, because the set of possible solutions is prohibitively large. The P.I. intends to investigate such problems through the approach of partition functions, the method inspired to a large extent by statistical physics. This will lead to new efficient algorithms in previously intractable problems.The particular problems addressed by the project include efficient computation of partition functions associated with perfect matching in (hyper)graphs, Hamiltonian cycles and cliques in graphs, graph homomorphisms, and systems of multivariate real quadratic equations. It will allow one to identify efficiently solvable cases of hard problems. For example, one will be able to efficiently distinguish graphs with sufficiently many (but still hard to find) Hamiltonian cycles from graphs that are sufficiently far away from Hamiltonian.