@ThomasKlimpel, I am trying to read this "Digital Memcomputing Machines" arXiv:1512.05064 ... do you see something more than parallelism there? (which could be realized with e.g. FPGA) ?

A decade ago I was considering non-standard approach with loop: electro-tech-online.com/threads/…

for a NP problem build a verifyier: circuit returning 1 for the proper input, 0 else

Now make a loop: send input+1 (cyclically) if wrong, input if right - such circuit with clock would test one input per cycle, until stopping in a satisfying input ...

But what if there is no clock? Just flow of electron trying to stabilize the flow by finding fixed point of the loop - solving our problem ... can it use some shortcut in finding the solution?

... but now I think it would just fluctuate between exponential number of local minima, very close to the global minimum solving our problem ...

@JarekDuda No, that was exactly the canonical objection to that paper. There is nothing more than parallelism there. The older UMM paper had some exponential information and time hidden inside, and that was why several people including Scott Aaronson refuted it. The DMM paper tried to address those critiques by no longer having those hidden exponential information and time, but that raised the question why not just simulate that system on a classical computer.

If the physical system is able to solve NP problems in polynomial time, then the simulation would also be able to do that. The big surprise is that the authors claim to have done exactly this simulation now, and that the resulting solver is faster then the current best in class MAX-SAT solvers. My reaction: Wow, now I no longer know what I should believe. Let me see what other people have to say...

One has to add that the initial paper didn't prove the absence of strange attractors and an other feature which would ruin the polynomial runtime, but they reported that those features never occurred in their experiments. So they were a bit more careful than in their UMM paper, in the sense that people like Scott Aaronson didn't need to refute their paper, if they wanted to make the point that P vs NP was still open.

(By the way, I have downloaded the strongly regular graphs and inspected them a bit. Interesting, exactly the very explicit and hands on approach I always try to recommend to people interested in such questions: Don't just develop big theories, test them with concrete examples and observe with your own eyes what actually happens.)

If it is just parallelism, you can do it e.g. with FPGA ... let's try to go back to the continuous-time loop computer question ...

I have originally thought about it for time-loops (e.g. using physics.stackexchange.com/questions/308106/… ) ... but this non-controversial version is also interesting to understand, definitely would strongly depend on technology used for the logic gates

(BTW, the graphical representation of strongly regular graphs turns out extremely symmetric, I couldn't find anything more than what we could get from information about the neighbors ... )

wow, Peter Shor has replied

@JarekDuda did you graph some regular graphs? what are you using them for? the classic hard problem for regular graphs is graph isomorphism which is presumably "not as hard" as NP complete...

So strongly regular graphs are the only really difficult for the graph isomorphism problem - it has turned out that they have nice graphical representation as regular polyhedrons ... but they are so regular that I couldn't squeeze anything from them ...

"on hold"??? why? this wasn't a controversial question - just about behavior of electric circuit ...

He has redrawn that survey shortly after publishing it on arXiv, with the words "Independent study work. Withdrawing since this submission was in bad taste". Anyway, his main homepage contains some relevant background information on his motivations.

Especially relevant is a blog post about Turing B-Type Machines, Reservoir Computation, Memristors, and Super-Turing Computation

I am quite happy now that I did not try to review that DMM paper back then. In fact, the survey of Daniel Saunders hinted to me that it would not be easy to refute that paper in the same cheap way as the UMM paper could be refuted. I don't see why he thinks that his submission was in "bad taste".