一、团队介绍

团队由永利集团经理许进教授领衔，核心成员包括李海生、余乐、刘小青、冷煌等骨干教师。团队长期致力于新型非图灵计算模型（如探针机、DNA计算）与专用计算机系统的研发。主要研究方向包括理论计算与组合数学、电子/DNA探针计算机、NP完全问题高效求解与应用。荣誉成果包括获国家自然科学二等奖1项，省部级一等奖3项，发表论文百余篇，出版《生物计算》、《自补图理论及其应用》、《极大平面图理论》等6部专著。

二、团队科研成果

1. 成果1提出了第一个非图灵机计算模型——探针机。

探针机是一种从底层全并行的数学计算模型，理论上，求解众多复杂难解的NP-完全问题只需一次探针运算。文章作为头版发表在2016年IEEE Trans. on Neural Net. And Learn Systems上，被IEEE学会评为当年3篇特色论文之一，亮点论文之首，也已被众多学者研究引用。

2. 成果2研制出人类首台非图灵非冯氏计算机—电子探针计算机

电子探针计算机(Electronic Probe Computer EPC)用于求解电子计算机不能有效求解的大规模复杂难解问题(NP-完全问题)，EPC采用的是串/并结合的计算模型。EPC由转编系统、输入/输出设备、图着色求解系统四部分构成。其中，转编系统是将待解问题转换为图着色问题的一个软件系统，图着色求解系统用于求解图着色问题。许进团队研发的EPC由4台柜机组成，60个FPGA卡，故把此EPC记为EPC60，如下图示：

用EPC60求解大规模图着色问题，其性能超越运行在工作站(AMD Ryzen™ 9 9950X 5.7GHz)上的当今主流求解器Gurobi。我们分别找到3个点数1000~2000的难解算例，用Gurobi在工作站很难在有效时间内给出解，但用EPC60可以快速给出解，见表1：

表1 EPC60与硅基计算机主流算法性能比较

顶点数	工作站上主流算法（Gurobi）	电子探针计算机 (EPC60)
1000的3-色图	8.3天	0.18秒
1500的3-色图	15天均未找到解	0.2秒
2000的3-色图		54秒

EPC具有高度的可扩展性，通过增加FPGA模块数量，能独立提升计算能力和并行处理性能。

EPC是通用型的探针计算机，实验数据表明，EPC具有可直接用来处理像蛋白质结构预测，天气预报，列车调度等这些电子计算机不能有效求解的应用问题。项目组正致力于从FPGA到芯片的研发，有望尽快市场化。

3. 成果3研发出首台彻底解决NP完全问题的DNA探针计算系统

许进从事生物计算研究始于1996年，至今30年，致力于耗能低、体积小、速度快的新型计算机的研发。提出非枚举DNA计算模型，并行DNA-计算模型，探针机等模型，发表学术论文百余篇，最近在Springs出版专著《Biological Computing》，中文版《生物计算》在国内出版。

 

其中，并行计算模型求解了61个顶点图的所有3-着色这一典型的NP完全问题，如下图示。此结果是迄今为止，生物计算中规模最大的一个算例，国际领先水平，获国家自然科学二等奖中的一个主要成果，计算复杂度到达359。

 

为彻底实现探针机模型以解决NP完全问题，团队进一步开发了DNA - 探针计算系统（DNA-Probe Computing System，DNA - PCS）求解上图中右图所示的114个顶点3-着色问题，复杂度为3114。该系统以探针机为计算模型，提出了阻断DNA探针技术，通过1次探针运算即可求出NP完全问题的所有解，充分发挥了DNA计算的天然并行性。研究结果表明，DNA - 探针计算系统凭借其并行架构与分子实现方式，突破了传统计算模型的局限，有望为诸如蛋白质结构预测、漏洞搜索和密码破译等复杂困难问题的求解开辟新途径。

这一系列成果在生物计算领域具有重要意义，为后摩尔时代新型计算模型的开发与应用奠定了坚实基础，也为未来生物型探针计算机的诞生提供了可能，有望成为人类计算史上的一次重大突破。

4. 成果4相关论文A special machine for solving NP-complete problems 以封面论文形式发表于Fundamental Research

论文阐述了传统图灵机的串行计算局限，为建立处理NP完全问题的有效算法，提出了第一个非图灵机计算模型探针机，并建立了DNA探针计算系统。在探针机模型的基础上，提出并实现了一种名为电子探针计算机（Electronic Probe Computer, EPC）的专用计算架构，研制出人类首台非图灵非冯氏计算机。在求解2048阶图的3-着色问题时，该计算机计算速度与求解精度显著超越当前主流全局优化算法。

此项成果标志着EPC在求解NP完全问题上实现革命性突破——首次为可抽象为NP完全问题的实际复杂场景提供快速通用型专用求解机器。为未来专用计算体系的设计开辟了新路径，推动计算技术向超并行、高维数据处理方向演进。

5. 成果5应用

应用1：探针计算机已在北京全路通信信号研究设计院集团有限公司得到应用，为超大型复杂轨道运营运输方案设计任务的完成提供了关键技术支撑；

应用2：许进教授团队与某国防科研机构合作，将探针计算机应用于无人机时空频域调度优化，为下一代空中智能系统的规模部署提供了核心技术支撑，为国家重大工程关键技术攻关作出了重要贡献。