A CNN SAT-solver robust to noise
Botond Molnár, Róbert Sumi, Mária Ercsey-Ravasz · 2014
In a recent study we presented a cellular neural network model for solving the Boolean satisfiability (SAT) problem. When solving hard problems the CNN presents transiently chaotic dynamics, raising the question of the viability of the system in presence of noise, which is unavoidable on analog devices. Here we test the robustness of the system in presence of white and colored (1/f2) noises. We also test the effects of potential errors in connection weights. The obtained results show that the probability of finding a solution is robust to noise and the developed CNN model tolerates surprisingly large noise intensities. Noise can even improve the performance by increasing the optimal parameter region of the model.