论文标题
从调查传播中学习：最大 - $ 3 $ -SAT的神经网络
Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
论文作者
论文摘要
许多自然优化问题都是NP措施，这意味着它们可能很难在最坏的情况下完全解决。但是，在实践中为所有（甚至大多数）实例获得合理的解决方案是足够的。本文提出了一种新的算法，用于以$ {θ（n}）$计算近似解决方案，以使用深度学习方法学使用最大的精确3-稳定性（max-e- $ 3 $ -SAT）问题。这种方法使我们能够创建一种能够通过使用调查传播算法获得的局部信息来固定布尔变量的学习算法。通过进行准确的分析，在随机的CNF实例中，最大$ 3 $ -SAT带有几个布尔变量，我们表明，即使没有找到消息的融合，这种新算法避免了任何拆卸策略，也可以比随机构建作业更好。尽管该算法与最先进的最大满意度（Max-SAT）求解器没有竞争力，但它可以解决比培训期间所看到的要大得多，更复杂的问题。
Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algorithm for computing approximate solutions in ${Θ(N})$ for the Maximum Exact 3-Satisfiability (MAX-E-$3$-SAT) problem by using deep learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random CNF instances of the MAX-E-$3$-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art Maximum Satisfiability (MAX-SAT) solvers, it can solve substantially larger and more complicated problems than it ever saw during training.
