Recent developments in approximate counting have made startling progress in developing fast algorithmic methods for approximating the number of solutions to constraint satisfaction problems (CSPs) with large arities, using connections to the Lovasz Local Lemma. Nevertheless, the boundaries of these methods for CSPs with non-Boolean domain are not well-understood. Our goal in this paper is to fill in this gap and obtain strong inapproximability results by studying the prototypical problem in this class of CSPs, hypergraph colourings. More precisely, we focus on the problem of approximately counting $q$-colourings on $K$-uniform hypergraphs with bounded degree $\Delta$. An efficient algorithm exists if $\Delta\lesssim \frac{q^{K/3-1}}{4^KK^2}$ (Jain, Pham, and Vuong, 2021; He, Sun, and Wu, 2021). Somewhat surprisingly however, a hardness bound is not known even for the easier problem of finding colourings. For the counting problem, the situation is even less clear and there is no evidence of the right constant controlling the growth of the exponent in terms of $K$. To this end, we first establish that for general $q$ computational hardness for finding a colouring on simple/linear hypergraphs occurs at $\Delta\gtrsim Kq^K$, almost matching the algorithm from the Lovasz Local Lemma. Our second and main contribution is to obtain a far more refined bound for the counting problem that goes well beyond the hardness of finding a colouring and which we conjecture that is asymptotically tight (up to constant factors). We show in particular that for all even $q\geq 4$ it is NP-hard to approximate the number of colourings when $\Delta\gtrsim q^{K/2}$.
翻译:近年的计算进展令人吃惊, 开发快速算法方法, 以近似于使用 Lovasz 局域Lemma 连接到 Lovasz 局域Lemma, 限制满意度问题( CSP ) 的解决方案数量惊人。 然而, 与非Boolean 域的 CSP 的这些方法的界限并不十分清楚。 我们本文的目标是填补这一差距, 通过研究 CSP 类中的原型问题, 高压颜色。 更确切地说, 我们关注的几乎是K美元 美元 的 美元 调值问题。 K- 调值的调值比 美元调值高。 如果 $ Delta\ smel\ frac{K/3-1 QQQQQ} (Jain, Pham, Vuong, 421 ; He, Sun, 和 Wu, 2021 。 然而, 令人惊讶的是, 我们甚至知道硬度问题是如何找到更简单的颜色的 。