“The paper is vague about how you train this thing.”
按年被提到
20152017 · 2 次2026
Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
用数字记忆计算机在多项式时间内求解素因数分解和 NP 难问题
Fabio L. Traversa, Massimiliano Di Ventra · 2015
声称由自组织逻辑门构成的 DMM 能以多项式资源求解 NP 问题
被提及 · 4 人首次 2015-12-18 · 最近 2017-12-27
4不同的人
3活跃月份
3讨论串
115被引(OpenAlex)
论文引入一类称为数字记忆计算机(DMM)的数字机器,声称它能以多项式资源(时间、空间、能量)解决包括 NP 问题在内的一大类问题。作者先为这类机器引入复杂度类,并借助动力系统理论得出多项式资源可解所需的物理约束,再提出基于自组织逻辑门与电路(SOLC,可从任意端子接受输入)的实现方案,并用泛函分析证明:SOLC 有全局吸引子,唯一平衡点即问题的解,且系统指数收敛、收敛速率随输入规模至多多项式增长。论文以素因数分解和子集和问题的 NP 难版本为例,并讨论其对 NP=P 问题的含义。
HN 为什么提它
评论者对其中“自组织逻辑门”如何求解布尔问题很感兴趣,也有人批评论文对怎么训练这种机器含糊其辞。
方法难度 5 / 5约 120 分钟经得起时间
读之前最好知道
1计算复杂性(P 与 NP)
2动力系统理论(吸引子、平衡点)
3忆阻器与数字逻辑电路
4泛函分析基础
学习路径
读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径先建立素因数分解为什么被视为难题、量子算法如何绕开它,再看同一作者组此前的 memcomputing 工作,最后读 DMM 的复杂度论证。
- 1
Shor 算法是「素因数分解可在多项式时间内解」的经典参照,DMM 论文拿它作对比对象。
读只抓结论:整数分解与离散对数在量子计算机上是多项式时间;不必深究量子傅里叶变换细节。
- 2
同一研究方向的前作,用集体态和多项式资源求解 NP 完全问题,DMM 是它的数字化、形式化版本。
读memcomputing 的基本思想(集体态、记忆元件)以及它如何用多项式资源求解子集和问题。
- 3Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
目标论文:定义 DMM 与其复杂度类,并声称可多项式资源求解分解和 NP 难问题。
读DMM 的数学定义与复杂度类、与动力系统理论的联系;阅读时留意其声称与已知复杂度理论的张力。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及批评Animats · 2017-12
引用marmaduke · 2017-12
“The magic seems to lie in the so called self organizing logic gates detailed”
指出其关键在于所谓的自组织逻辑门
被提交为 story · 2 次
- Digital Memcomputing Machines: Strong Evidence That P=NP ↗iamed2 · 2015-12-18 · 2 分
- Polynomial-Time Solution to an NP-Hard Problem with Digital Memcomputing Machine ↗cbennett · 2016-01-10 · 4 分