按年被提到
20172017 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1710.09278 · cs.AI

Evidence of an exponential speed-up in the solution of hard optimization problems

Fabio L. Traversa, Pietro Cicotti, Forrest Sheldon, Massimiliano Di Ventra · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2017-10-29 · 最近 2017-12-27
2不同的人
2活跃月份
2讨论串
53被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Optimization problems pervade essentially every scientific discipline and industry. Many such problems require finding a solution that maximizes the number of constraints satisfied. Often, these problems are particularly difficult to solve because they belong to the NP-hard class, namely algorithms that always find a solution in polynomial time are not known. Over the past decades, research has focused on developing heuristic approaches that attempt to find an approximation to the solution. However, despite numerous research efforts, in many cases even approximations to the optimal solution are hard to find, as the computational time for further refining a candidate solution grows exponentially with input size. Here, we show a non-combinatorial approach to hard optimization problems that achieves an exponential speed-up and finds better approximations than the current state-of-the-art. First, we map the optimization problem into a boolean circuit made of specially designed, self-organizing logic gates, which can be built with (non-quantum) electronic components; the equilibrium points of the circuit represent the approximation to the problem at hand. Then, we solve its associated non-linear ordinary differential equations numerically, towards the equilibrium points. We demonstrate this exponential gain by comparing a sequential MatLab implementation of our solver with the winners of the 2016 Max-SAT competition on a variety of hard optimization instances. We show empirical evidence that our solver scales linearly with the size of the problem, both in time and memory, and argue that this property derives from the collective behavior of the simulated physical circuit. Our approach can be applied to other types of optimization problems and the results presented here have far-reaching consequences in many fields.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

没有评论直接链到它;下面是它被提交的讨论串里回复最多的评论(不计入统计)
讨论串评论Animats · 2017-12

“This is really important if not bogus. Any comments from people in the field? It's like back-propagation for digital logic.”

Evidence of exponential speed-up in the solution of hard optimization problems?原评论 ↗
讨论串评论zmonx · 2017-12

“The 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”

Evidence of exponential speed-up in the solution of hard optimization problems?原评论 ↗
讨论串评论ColinWright · 2017-12

“Quoting from the abstract: >... a non-combinatorial approach > to hard optimization problems that >... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver sca…”

Evidence of exponential speed-up in the solution of hard optimization problems?原评论 ↗
被提交为 story · 2 次