论文标题
制定振荡器风格的动力系统来解决布尔值满意
Formulating Oscillator-Inspired Dynamical Systems to Solve Boolean Satisfiability
论文作者
论文摘要
动态系统可以提供一种新型的非树先计算方法。具体而言，系统中能量的自然最小化是最小化组合优化问题的目标功能的宝贵特性，其中许多使用常规数字求解器仍然具有挑战性。在这项工作中，我们制定了两个振荡器启发的动力学系统，以解决布尔满意度（SAT）中典型的计算问题。系统动力学经过设计，使它们促进了解决SAT问题的两种不同口味的解决方案。我们制定了第一个动态系统来计算解决3-SAT问题的解决方案，而对于第二个系统，我们显示其动力学映射到Max-Nae-3-SAT问题的解决方案。我们的工作进一步了解了如何使用这种物理启发的方法来解决计算中具有挑战性的问题。
Dynamical systems can offer a novel non-Boolean approach to computing. Specifically, the natural minimization of energy in the system is a valuable property for minimizing the objective functions of combinatorial optimization problems, many of which are still challenging to solve using conventional digital solvers. In this work, we formulate two oscillator-inspired dynamical systems to solve quintessential computationally intractable problems in Boolean satisfiability (SAT). The system dynamics are engineered such that they facilitate solutions to two different flavors of the SAT problem. We formulate the first dynamical system to compute the solution to the 3-SAT problem, while for the second system, we show that its dynamics map to the solution of the Max-NAE-3-SAT problem. Our work advances understanding of how this physics-inspired approach can be used to address challenging problems in computing.
