NORDITA and AlbaNova University Centre, Department of Computational Biology, KTH-Royal Institute of Technology and Stockholm University, Roslagstullsbacken 23, SE-10691 Stockholm, Sweden.
Dipartimento di Fisica, Sapienza Università di Roma and Istituto Nazionale di Fisica Nucleare, Sezione di Roma1 and CNR-Nanotec, Unità di Roma, P.le Aldo Moro 5, I-00185 Roma, Italy.
Nat Commun. 2016 Oct 3;7:12996. doi: 10.1038/ncomms12996.
Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very large instances. Moreover, it is still unclear what are the key features that make a discrete combinatorial optimization problem hard to solve. Here we study random K-satisfiability problems with K=3,4, which are known to be very hard close to the SAT-UNSAT threshold, where problems stop having solutions. We show that the backtracking survey propagation algorithm, in a time practically linear in the problem size, is able to find solutions very close to the threshold, in a region unreachable by any other algorithm. All solutions found have no frozen variables, thus supporting the conjecture that only unfrozen solutions can be found in linear time, and that a problem becomes impossible to solve in linear time when all solutions contain frozen variables.
离散组合优化在许多科学学科中起着核心作用，然而，对于困难问题，我们缺乏能够解决非常大规模实例的线性时间算法。此外，目前还不清楚是什么关键特征使得离散组合优化问题难以解决。在这里，我们研究了 K=3、4 的随机 K-可满足性问题，这些问题在接近 SAT-UNSAT 阈值时被认为非常困难，此时问题停止存在解决方案。我们表明，回溯传播算法在实际线性时间内，可以在任何其他算法无法到达的区域中，找到非常接近阈值的解决方案。所有找到的解决方案都没有冻结变量，这支持了只有非冻结解决方案才能在线性时间内找到的猜想，并且当所有解决方案都包含冻结变量时，问题将无法在线性时间内解决。
