The last time Hackerfall tried to access this page, it returned a not found error.
A cached version of the page is below, or click here to continue anyway

Early days, but this is a potential bomb.

If we solve NP-complete efficiently then we may break TSP and all sorts of magical optimisation problems joyously drop out of the sky at our feet. It

is not clear if this would also break integer factorisationand thus RSA, but perhaps it might.

A slightly updated version (7 July 2015) of this paper is available on arxiv

here.

In the the abstract you'll read this,

"We 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."

That makes the paper exciting.

This is perhaps a little bit beyond factoring the number 15,

as IBM did with a quantum implementation in 2001, but the smallishly sized subset-sum problem (SSP) example in the paper is nevertheless toyish. Popping out a magical solution to SSP doesn't necessarily mean that the reduction mechanism can be used for all NP-complete brethren.

There has been much noise and history in this space that has collapsed on further inspection, especially regarding physical models of computation.

You can read

Aaronson's 2005 survey paperon various techniques for solving NP-complete problems in polynomial time which is critical of all techniques including quantum. The community now seems convinced quantum may indeed work so perhaps Aaronson has to be taken with a grain of salt.

that cites Aaronson's paper was published on 22nd April 2015.

When I tweeted about the SSP paper @jhonline92 quickly noted: potential issues with time / space complexity; if SSP is always solved; and, if other NP-complete problems could be similarly reduced in this model. Very good points and those issues are consistent with the critical review from Markov above.

D-Wave

is arguably not a true quantum computerin that it couldn't run Shor's algo for factoring though Shor's algo is perhaps

not the only way to factorand thus break RSA. Likewise, to be useful perhaps not all NP-complete problems may need to be solved for a memprocessor.

Extraordinary claims need extraordinary proof. There should be some scepticism about the SSP memcomputing paper as it may just be another notch in the belt of history regarding failed analogue attempts to breakdown NP-complete. It is different though. Is it different enough?

Let's see what happens...

--Matt.