Directed Percolation and Numerical Stability of Simulations of Digital MemComputing Machines*

Digital MemComputing Machines (DMMs) are a novel, non-Turing class of machines designed to solve combinatorial optimization problems. They can be physically realized with continuous-time, non-quantum dynamical systems with memory, whose ordinary differential equations (ODEs) can be numerically integrated on modern computers. Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs, showing substantial advantages over state-of-the-art solvers. Using 3-SAT with planted solutions as an explicit example, we show that, despite the stiffness of these ODEs, our simulations are robust as long as the integration scheme preserves the critical points of the ODEs, and an "unsolvable-solvable transition" is observed when decreasing the integration time step Δt near a critical Δt_c. To explain these results, we model the dynamical behavior of DMMs as a directed percolation of the state trajectory in the phase space in the presence of noise. This point of view clarifies the reasons behind their numerical robustness and provides an analytical understanding of the unsolvable-solvable transition. These results land further support to the usefulness of DMMs in the solution of hard combinatorial optimization problems.