Dec 16, 2015
Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
Fabio Lorenzo Traversa, Massimiliano Di Ventra
We introduce a class of digital machines, we name Digital Memcomputing Machines, (DMMs) able to solve a wide range of problems including Non-deterministic Polynomial (NP) ones with polynomial resources (in time, space, and energy). An abstract DMM with this power must satisfy a set of compatible mathematical constraints underlying its practical realization. We prove this by making a connection with the dynamical systems theory. This leads us to a set of physical constraints for poly-resource resolvability. Once the mathematical requirements have been assessed, we propose a practical scheme to solve the above class of problems based on the novel concept …
[searchandfilter fields=”post_tag”]