按年被提到
20152017 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:1512.05064 · cs.ET

Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines

用数字记忆计算机在多项式时间内求解素因数分解和 NP 难问题
Fabio L. Traversa, Massimiliano Di Ventra · 2015

声称由自组织逻辑门构成的 DMM 能以多项式资源求解 NP 问题

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 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. 1
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    Shor 算法是「素因数分解可在多项式时间内解」的经典参照,DMM 论文拿它作对比对象。

    读只抓结论:整数分解与离散对数在量子计算机上是多项式时间;不必深究量子傅里叶变换细节。

  2. 2

    同一研究方向的前作,用集体态和多项式资源求解 NP 完全问题,DMM 是它的数字化、形式化版本。

    读memcomputing 的基本思想(集体态、记忆元件)以及它如何用多项式资源求解子集和问题。

  3. 3
    Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines用数字记忆计算机在多项式时间内求解素因数分解和 NP 难问题 · 2015 · 就是这篇

    目标论文:定义 DMM 与其复杂度类,并声称可多项式资源求解分解和 NP 难问题。

    读DMM 的数学定义与复杂度类、与动力系统理论的联系;阅读时留意其声称与已知复杂度理论的张力。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
批评Animats · 2017-12

“The paper is vague about how you train this thing.”

Evidence of exponential speed-up in the solution of hard optimization problems?原评论 ↗
引用marmaduke · 2017-12

“The magic seems to lie in the so called self organizing logic gates detailed”

指出其关键在于所谓的自组织逻辑门
Evidence of exponential speed-up in the solution of hard optimization problems?原评论 ↗
被提交为 story · 2 次