Confirmation of Exponential Speed-up Using MemComputing to Solve Hard Optimization Problems
Optimization is a core component of every databased scientific discipline and industry. However, the explosive growth of Big Data combined with classical computing architecture can cause significant issues in solving optimization problems. The difficulty of computation is especially prominent in a set of problems classified as NP-hard. Currently, no algorithm exists for NP-hard problems that is able to find a solution in polynomial time.
Furthermore, even reaching approximations to an optimal solution is challenging to discover for the most difficult optimization problems. This is because as the number of inputs and constraints increase linearly, the computational time needed to find an approximation to the optimal solution can grow exponentially. It is common in industry for a single problem to take days, even weeks, to run. This is extreme, but obviously highlights the value of the information provided. There are also plenty of problems that could take months, years, decades or more. However, in most cases, it is not viable to wait this long or pay for that much computation time.
This document discusses how MemComputing exploits the physical properties of classical computer architectures to bypass these exceedingly long computations and provide results orders of magnitude faster than today’s best algorithms. We also highlight results from a benchmark test where MemComputing was able to resolve a problem that would take today’s best solvers many times the age of the universe. This demonstrates that MemComputing enables industry to approach computations that were previously impossible to effectively approximate.