Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines

Abstract

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 initially prove this by introducing the complexity classes for these machines. We then make a connection with dynamical systems theory. This leads to the 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 of self-organizing logic gates and circuits (SOLCs). These are logic gates and circuits able to accept input signals from any terminal, without distinction between conventional input and output terminals. They can solve boolean problems by self-organizing into their solution. They can be fabricated either with circuit elements with memory (such as memristors) and/or standard MOS technology. Using tools of functional analysis, we prove mathematically the following constraints for the poly-resource resolvability: i) SOLCs possess a global attractor; ii) their only equilibrium points are the solutions of the problems to solve; iii) the system converges exponentially fast to the solutions; iv) the equilibrium convergence rate scales at most polynomially with input size. We finally provide arguments that periodic orbits and strange attractors cannot coexist with equilibria. As examples we show how to solve the prime factorization and the NP-hard version of the subset-sum problem. Since DMMs map integers into integers they are robust against noise, and hence scalable. We finally discuss the implications of the DMM realization through SOLCs to the NP=P question related to...

References in corpus (4)

• Memory effects in complex materials and nanoscale systems
• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Quantum Memristors
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states

Cited by in corpus (40)

• Stochastic p-bits for Invertible Logic
• p-Bits for Probabilistic Spin Logic
• The promise of spintronics for unconventional computing
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Hardware emulation of stochastic p-bits for invertible logic
• Memcomputing: Leveraging memory and physics to compute efficiently
• Low Barrier Nanomagnets as p-bits for Spin Logic
• Roadmap for Unconventional Computing with Nanotechnology
• Weighted p-bits for FPGA implementation of probabilistic circuits
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Topological field theory and computing with instantons
• Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
• Absence of chaos in Digital Memcomputing Machines with solutions
• The complex dynamics of memristive circuits: analytical results and universal slow relaxation
• Instantons in self-organizing logic gates
• Digital Memcomputing: from Logic to Dynamics to Topology
• Directed percolation and numerical stability of simulations of digital memcomputing machines
• On the Universality of Memcomputing Machines
• Critical branching processes in digital memcomputing machines
• Nanomagnetic Self-Organizing Logic Gates
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Voltage-driven Building Block for Hardware Belief Networks
• Artificial Spin Ice Phase-Change Memory Resistors
• Memristive Networks: from Graph Theory to Statistical Physics
• Memcomputing Numerical Inversion with Self-Organizing Logic Gates
• The mise en scene of memristive networks: effective memory, dynamics and learning
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Hardware implementation of digital memcomputing on small-size FPGAs
• Non-equilibrium criticality and efficient exploration of glassy landscapes with memory dynamics
• Projective Embedding of Dynamical Systems: uniform mean field equations
• Fully parallel implementation of digital memcomputing on FPGA
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• Lorentz Quantum Computer
• MemComputing vs. Quantum Computing: some analogies and major differences
• On the solvable-unsolvable transition due to noise-induced chaos in digital memcomputing
• Acceleration of digital memcomputing by jumps
• Brain-like features of MemComputing machines