  Optimization problems pervade essentially every scientific discipline and
industry. Many such problems require finding a solution that maximizes the
number of constraints satisfied. Often, these problems are particularly
difficult to solve because they belong to the NP-hard class, namely algorithms
that always find a solution in polynomial time are not known. Over the past
decades, research has focused on developing heuristic approaches that attempt
to find an approximation to the solution. However, despite numerous research
efforts, in many cases even approximations to the optimal solution are hard to
find, as the computational time for further refining a candidate solution grows
exponentially with input size. Here, we show a non-combinatorial approach to
hard optimization problems that achieves an exponential speed-up and finds
better approximations than the current state-of-the-art. First, we map the
optimization problem into a boolean circuit made of specially designed,
self-organizing logic gates, which can be built with (non-quantum) electronic
components; the equilibrium points of the circuit represent the approximation
to the problem at hand. Then, we solve its associated non-linear ordinary
differential equations numerically, towards the equilibrium points. We
demonstrate this exponential gain by comparing a sequential MatLab
implementation of our solver with the winners of the 2016 Max-SAT competition
on a variety of hard optimization instances. We show empirical evidence that
our solver scales linearly with the size of the problem, both in time and
memory, and argue that this property derives from the collective behavior of
the simulated physical circuit. Our approach can be applied to other types of
optimization problems and the results presented here have far-reaching
consequences in many fields.
