Efficient solution of Boolean satisfiability problems with digital memcomputing.

Area of Science:

• Computational physics
• Theoretical computer science
• Applied mathematics

Background:

• Boolean satisfiability (SAT) is a fundamental problem in logic with broad applications.
• Solving SAT is computationally challenging, often requiring exponential time for worst-case and typical instances.
• Existing algorithms struggle with hard SAT problem instances.

Purpose of the Study:

• To introduce a novel memory-assisted physical system for solving SAT problems.
• To demonstrate the system's efficiency and scalability for hard SAT instances.
• To analytically prove the system's capability for efficient continuous-time SAT solving.

Main Methods:

• Numerical integration of non-linear ordinary differential equations of a digital memcomputing machine.
• Analytical demonstration of efficient continuous-time SAT problem solving.
• Analysis of collective dynamical properties for solution guidance.

Main Results:

• The memcomputing machine shows evidence of polynomially-bounded scalability for hard SAT instances.
• The system efficiently solves SAT in continuous time without chaos or exponentially growing energy.
• Numerical simulations demonstrate robustness against errors due to persistent dynamical properties.

Conclusions:

• Physics-inspired computing offers a promising avenue for tackling computationally hard problems like SAT.
• The developed memory-assisted system provides an efficient and scalable solution for SAT.
• This work encourages further research in physics-inspired computing paradigms, from theory to hardware.