Computational problem hardness changes predict algorithm speed limits
Fine-Grained Complexity Across the Computational Phase Transition
Computational ComplexityData Structures and Algorithms
Summary
This paper studies how a problem that’s easy to solve suddenly becomes very hard as some parameter changes. The authors focus on a specific statistical physics model, the hard-core model, and show exactly how the time it takes to solve it gets longer when the problem moves past a certain critical point. They also connect improvements in solving this problem to faster methods for solving another famous problem in computer science, SAT. Their work clarifies the precise border where problems become harder and what that means for algorithm designers.
What this means in practice
- •For algorithm designers: Identify theoretical limits on how fast sampling and counting algorithms can run when dealing with problems near critical complexity thresholds.
- •For optimization software developers: Use the fine-grained complexity insights to understand when improved approximate counting methods could speed up solving constraint satisfaction problems like SAT.
A theory result. No direct application yet.
Authors
Zhe Ju, Jingcheng Liu, Yitong Yin
Abstract
How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.