Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing

Abstract

Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving "hard" planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.

References in corpus (15)

• The Entropy of the K-Satisfiability Problem
• Survey propagation: an algorithm for satisfiability
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Memcomputing: Leveraging memory and physics to compute efficiently
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Topological field theory and computing with instantons
• Absence of chaos in Digital Memcomputing Machines with solutions
• Instantons in self-organizing logic gates
• Digital Memcomputing: from Logic to Dynamics to Topology
• Critical branching processes in digital memcomputing machines
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Some remarks on the survey decimation algorithm for K-satisfiability
• Memcomputing Numerical Inversion with Self-Organizing Logic Gates
• Streamlining Variational Inference for Constraint Satisfaction Problems

Cited by in corpus (11)

• Roadmap for Unconventional Computing with Nanotechnology
• Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Efficient Probabilistic Computing with Stochastic Perovskite Nickelates
• Directed percolation and numerical stability of simulations of digital memcomputing machines
• Hardware implementation of digital memcomputing on small-size FPGAs
• Fully parallel implementation of digital memcomputing on FPGA
• Non-equilibrium criticality and efficient exploration of glassy landscapes with memory dynamics
• SPICE Modeling of Memcomputing Logic Gates
• Acceleration of digital memcomputing by jumps
• On the solvable-unsolvable transition due to noise-induced chaos in digital memcomputing
• Necessary and Sufficient Condition for Satisfiability of a Boolean Formula in CNF and its Implications on P versus NP problem