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

Meanderful: Breaking NP-completeness without quantum?

Early days, but this is a potential bomb.

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

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 factorisation

and thus RSA, but perhaps it might.

[2]

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 paper

on 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.

Update: See [1][4] A critical review of the Memcomputing paper by Igor Markov

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 computer

in that it couldn't run Shor's algo for factoring though Shor's algo is perhaps

not the only way to factor

and 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.

PS: Well, that escalated quickly. A few thousand people read this last night and some provided some healthy commentary. The conclusion voiced being that the SSP paper above doesn't really stand up and it is another failed analogue attempt at breaking down NP-complete as consistent with Aaronson's point of view. [1] Update: Here is Scott Aaronson's well written blog with specific consideration and refuting of the Memcomputing SSP paper. Interestingly in that blog post Aaronson holds his line on the belief that quantum computing will also not work for NP-complete problems which seems reasonable. [2] Update: I'm told that integer factorisation will break if NP-complete breaks, so yeah, RSA would also fall. [3] Update: A simplified summary by Scott Aaronson from SciAm and references to his BQP notes in his lecture notes. [4] Update: I've misunderstood Aaronson. He is supportive of quantum for factorisation (as part of BQP) but points out that quantum will not be able to do NP-complete and I've not seen any reference to work suggesting otherwise.

Continue reading on meanderful.blogspot.com