  It is well known that physical phenomena may be of great help in computing
some difficult problems efficiently. A typical example is prime factorization
that may be solved in polynomial time by exploiting quantum entanglement on a
quantum computer. There are, however, other types of (non-quantum) physical
properties that one may leverage to compute efficiently a wide range of hard
problems. In this perspective we discuss how to employ one such property,
memory (time non-locality), in a novel physics-based approach to computation:
Memcomputing. In particular, we focus on digital memcomputing machines (DMMs)
that are scalable. DMMs can be realized with non-linear dynamical systems with
memory. The latter property allows the realization of a new type of Boolean
logic, one that is self-organizing. Self-organizing logic gates are
"terminal-agnostic", namely they do not distinguish between input and output
terminals. When appropriately assembled to represent a given
combinatorial/optimization problem, the corresponding self-organizing circuit
converges to the equilibrium points that express the solutions of the problem
at hand. In doing so, DMMs take advantage of the long-range order that develops
during the transient dynamics. This collective dynamical behavior, reminiscent
of a phase transition, or even the "edge of chaos", is mediated by families of
classical trajectories (instantons) that connect critical points of increasing
stability in the system's phase space. The topological character of the
solution search renders DMMs robust against noise and structural disorder.
Since DMMs are non-quantum systems described by ordinary differential
equations, not only can they be built in hardware with available technology,
they can also be simulated efficiently on modern classical computers. As an
example, we will show the polynomial-time solution of the subset-sum problem
for the worst...
