Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states

Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proven mathematically that memcomputing machines have the same computational power of nondeterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size. The reason for this computational power stems from properties inspired by the brain and shared by any universal memcomputing machine, in particular intrinsic parallelism and information overhead, namely, the capability of compressing information in the collective state of the memprocessor network.

Researchers show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem. They have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting. Although the particular machine presented here is eventually limited by noise—and will thus require error-correcting codes to scale to an arbitrary number of memprocessors—it represents the first proof of concept of a machine capable of working with the collective state of interacting memory cells, unlike the present-day single-state machines built using the von Neumann architecture.

Scheme of the memcomputing architecture used in this work to solve the subset sum problem.

Universal memcomputing machines are nondeterministic Turing Machines that can be fabricated

There are several classes of computational problems that require time and resources that grow exponentially with the input size when solved. This is true when these problems are solved with deterministic Turing machines, namely, machines based on the well-known Turing paradigm of computation, which is at the heart of any computer we use nowadays. Prototypical examples of these difficult problems are those belonging to the class that can be solved in polynomial (P) time if a hypothetical Turing machine—named nondeterministic Turing machine—could be built. They are classified as nondeterministic polynomial (NP) problems, and the machine is hypothetical because, unlike a deterministic Turing machine, it requires a fictitious “oracle” that chooses which path the machine needs to follow to get to an appropriate state. To date, it is not known whether NP problems can be solved in polynomial time by a deterministic Turing machine. If that were the case, we could finally provide an answer to the most outstanding question in computer science, namely, whether NP = P.

Recently, a new paradigm, named “memcomputing”, has been advanced. It is based on the brain-like notion that one can process and store information within the same units (memprocessors) by means of their mutual interactions. This paradigm has its mathematical foundations on an ideal machine, alternative to the Turing one, that was formally introduced by two of the authors (F.T. and M.D.) and dubbed “universal memcomputing machine (UMM)”. It has been proven mathematically that UMMs have the same computational power of a nondeterministic Turing machine, but unlike the latter, UMMs are fully deterministic machines and, as such, they can actually be fabricated. A UMM owes its computational power to three main properties: intrinsic parallelism—interacting memory cells simultaneously and collectively change their states when performing computation; functional polymorphism—depending on the applied signals, the same interacting memory cells can calculate different functions; and finally, information overhead—a group of interacting memory cells can store a quantity of information that is not simply proportional to the number of memory cells itself.

These properties ultimately derive from a different type of architecture: the topology of memcomputing machines is defined by a network of interacting memory cells (memprocessors), and the dynamics of this network are described by a collective state that can be used to store and process information simultaneously. This collective state is reminiscent of the collective (entangled) state of many qubits in quantum computation, where the entangled state is used to solve efficiently certain types of problems such as factorization. Here, we prove experimentally that such collective states can also be implemented in classical systems by fabricating appropriate networks of memprocessors, thus creating either linear or nonlinear combinations out of the states of each memprocessor. The result is the first proof of concept of a machine able to solve an NP-complete problem in polynomial time using collective states.

The experimental realization of the memcomputing machine presented here, and theoretically proposed in another paper, can solve the NP-complete version of the subset sum problem (SSP) in polynomial time with polynomial resources.

The subset sum problem (SSP) is a problem as follows: if we consider a finite set G ∈ Z of cardinality n, is there a non-empty subset K ∈ G whose sum is a given integer number s?

The machine they have built is analog and hence would be scalable to very large numbers of memprocessors only in the absence of noise or using some error-correcting codes.

In summary, we have demonstrated experimentally a deterministic memcomputing machine that is able to solve an N P -complete problem in polynomial time (actually in one step) using only polynomial resources. The actual machine we built clearly suffers from technological limitations, that impair its scalability due to unavoidable noise. These limitations derive from the fact that we encode the information directly into frequencies, and so ultimately into energy. This issue could, however, be overcome either using error correcting codes or with other UMMs that use other ways to encode such information and are digital at least in their input and output. Irrespective, this machine represents the first experimental realization of a UMM that uses the collective state of the whole memprocessor network to exploit the information overhead. Finally, it is worth mentioning that the machine we have fabricated is not a general purpose one. However, other realizations of UMMs are general purpose and can be easily built with available technology. Their practical realization would thus be a powerful alternative to current Turing-like machines.

SOURCE – Science Advances