一种从“骨子里”并行的NP完全问题专用计算机——探针计算机研制成功。该计算机仅搭载60个探针计算卡，即可高效处理搜索空间达3的2048次方的复杂问题，求解性能显著超越国际主流优化求解器——Gurobi，为当前最快的专用计算机。其主要特点：
并行计算模型：区别于基于串行计算的经典图灵机，探针计算机采用了全新的底层并行计算模型——拟探针机。
存算一体架构：该计算机无独立的存储单元，存算一体化，从根本上解决了现有求解器（如Gurobi）所面临的“存储墙”瓶颈。
易于扩展：各探针计算卡相互独立工作，可通过直接增加卡的数量进行灵活扩展，且对现有系统无影响。
广泛适用性：其架构原理决定了它能够有效应用于求解所有NP完全问题。
中文标题：国际首台非图灵非冯氏专用计算机——探针计算机，以最快性能重磅问世！
英文原题：A special machine for solving NP-complete problems
第一作者：
许 进，北京大学
余 乐，北京工商大学
杨慧慧，中南大学
通讯作者：
刘小青，北京大学计算机学院
冷 煌，北京大学计算机学院
邵泽辉，广州大学计算科技研究院
关键词：探针计算机；NP完全问题；体系结构；并行
研究背景
在计算机科学中，有一类特别难解的问题，即NP完全问题。这类问题有个“要命”的特点：问题规模稍微扩大，计算量就会爆炸式增长。NP问题无处不在且威力惊人，从路径规划到基因测序，从蛋白质折叠到生产调度，问题规模稍增，计算需求便呈指数级飙升。
为什么电子计算机难以高效解决NP问题？许进教授研究团队自2002年以来的系统研究表明，其根本制约来自两个方面：一是物理极限，硅基芯片3nm工艺已接近原子尺度，量子隧穿效应导致漏电和散热问题，使摩尔定律濒临失效；一是理论局限，传统图灵机模型存在双重约束，即线性数据放置模式和串行运算方式，从结绳记事到现代计算机，数据始终采用“一个挨一个”的线性排列，每次仅能处理相邻数据。
研究成果
创新性地提出了一种面向NP完全问题的高效求解方案——探针计算机（图1）。在计算模型设计上，采用图的顶点作为基本计算单元；提出3-色图分类方法，将问题划分为4个可并行处理的类别；设计7种完全并行的探针算子，每个算子独立执行运算，消除算子间等待开销，在尽可能规避无效解空间的同时，实现底层大规模并行计算。
基于该计算模型，成功研制出求解NP完全问题的专用探针计算机（EPC），主要技术特性如下：
系统架构
EPC采用异构协同计算架构（图2，串行控制流+并行数据流），核心模块包括：控制层，将待解问题转换为图着色问题、格式转换、以及任务分发等功能；光路由层，由若干光路由卡组成；探针计算层，由60个探针计算卡构成可扩展计算集群。
能力与特点
能力测试：将EPC与当前性能最优的优化求解器之一Gurobi进行了对比实验，选取开源数据集中1000~2000阶的3-色图作为测试案例。
在2000个顶点规模的100个随机图的3-着色问题测试集中，EPC运行时间3430秒，获得所有最优解；在工作站运行Gurobi，用时至少需要43571秒，成功率仅有5~6%。
在1000个顶点规模的1000个随机图的3-着色问题测试集中，EPC计算用时为4154秒，成功率98.2%；而Gurobi用时至少需要61374秒，成功率仅有54.3%。
工作站CPU为AMD Ryzen™ 9 9950X，主频最高5.7GHZ。
规模可扩展性：EPC采用模块化可扩展架构，实现即插即用扩展，使计算能力更强。
目前EPC可用于求解规模≤2048的3-着色问题，现有优化求解器虽在小规模组合问题上表现优异，但在处理较大规模问题时面临计算瓶颈。相比之下，EPC展现出良好的可扩展性，为解决大规模NP问题提供一种新的可行路径。
未来方向
许进教授研究团队正推进探针计算机的系统升级：一方面拓展可计算的问题规模，另一方面积极研发新一代探针计算芯片。
主要作者简介
许 进 北京大学教授，北京工商大学计算机与人工智能学院院长。主要从事理论计算机、生物计算、图论与组合优化研究。以第一完成人获国家自然科学二等奖1项，教育部和湖北省自然科学一等奖3项。
余 乐 北京工商大学副教授。主要研究领域为智能计算系统，神经网络芯片，大模型及其在金融领域的应用。
杨慧慧 中南大学博士研究生。主要研究方向为新型计算，神经生物学。
刘小青 北京大学计算机学院特聘副研究员。研究方向为图论与组合优化，新型计算。
冷 煌 北京大学计算机学院特聘副研究员。研究方向为强化学习、图论、新型计算。
邵泽辉 广州大学计算科技研究院教授。主要从事模式识别、智能信息处理、图论及应用、算法设计与分析相关领域工作。
引用本文
Jin Xu, Le Yu, Huihui Yang, Siyuan Ji, et al., A special machine for solving NP-complete problems. Fundamental Research. 5(4) (2025) 1743-1749.
原文链接（复制到浏览器中查看）: https://www.sciencedirect.com/science/article/pii/S2667325825002997
期刊主页：
www.keaipublishing.com/en/journals/fundamental-research/
文章阅读：
www.sciencedirect.com/journal/Fundamental-Research
投稿系统：
www.editorialmanager.com/fmre
查看更多本期信息，点击文末“阅读原文”，欢迎阅读、下载及引用！
转载本文请联系原作者获取授权，同时请注明本文来自科爱KeAi科学网博客。
链接地址：https://wap.sciencenet.cn/blog-3496796-1506822.html?mobile=1
收藏
