Oscillator-Inspired Dynamical Systems to Solve Boolean Satisfiability

Abstract

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 design 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-not-all-equal (NAE)-3-SAT problem. Our work advances our understanding of how this physics-inspired approach can be used to address challenging problems in computing.

Keywords

• Boolean satisfiability (SAT)
• combinatorial optimization
• dynamical system
• Max-not-all-equal (NAE)-SAT
• oscillator