Evidence of exponential speed-up in the solution of hard optimization problems?
1–10 of 41 posts
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#2This is really important if not bogus. Any comments from people in the field?
It's like back-propagation for digital logic.
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#3This is really important if not bogus. Any comments from people in the field? It's like back-propagation for digital logic.
"Huge if true"
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#4This is really important if not bogus. Any comments from people in the field? It's like back-propagation for digital logic.
Did you look at the paper or just throwing the analogy out there? It seems the described problems are integer programming which wouldn’t have gradients as in back propagation.
The magic seems to lie in the so called self organizing logic gates detailed
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#5This is really important if not bogus. Any comments from people in the field? It's like back-propagation for digital logic.
Looking at the authors papers it doesn't look worth reading.
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#6Can someone provide a technical tldr. I'm afraid this is over my head, but I'm extremely curious as I understand it's importance.
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#7The authors have built a start-up based on these ideas:
They provide their SAT solver as a service that you can try.
A related paper I recommend in this context is NP-complete Problems and Physical Reality by Scott Aaronson:
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#8Can someone provide a technical tldr. I'm afraid this is over my head, but I'm extremely curious as I understand it's importance.
My initial instinct is not very important, but we will wait and see.
There have been many, many examples of people achieving significant improvements on many classes of NP-complete problems, and more come out every year, of course the more general your improvement the better. Modern SAT solvers with learning are such an improvement.
The claim of "exponential" seems very dodgy to me, they are running over a fixed set of benchmarks, it's hard to measure an exponential improvement over such a set.
I will wait until I see this peer reviewed, after a brief skim read I am a little worried about how big the circuits they are making are.
EDIT: they mostly compare against 3 specially crafted classes of random problems. Noone really cares about random problems, and it looks to me like they made random problems their system would be particularly good at dealing with. That sets off alarm bells for me.
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#9This keeps popping up every few months for several years, and seems like BS. Here's an example:
https://news.ycombinator.com/item?id=8652475
And here's Scott Aaronson's debunking:
https://www.scottaaronson.com/blog/?p=2212
If these guys could really solve NP complete problems, they should have some amazing concrete results to show at this point, which they don't.
Re: Evidence of exponential speed-up in the solution of hard optimization problems?
#10The authors have built a start-up based on these ideas: http://memcpu.com/ They provide their SAT solver as a service that you can try. A related paper I recommend in this context is NP-complete Problems and Physical Reality by Scott Aaronson: https://www.scottaaronson.com/papers/npcomplete.pdf
It's worth noting that Scott Aaronson has commented on previous work by the same authors: https://www.scottaaronson.com/blog/?p=2212 . At the time, he was convinced that their approach wouldn't scale. I'm not sure about their current approach, but at a glance it seems similar to the previous one.
Previous work: https://arxiv.org/pdf/1411.4798.pdf