Breakthrough in Solving NP-Complete Problems Using Electronic Probe Computers
-
摘要: 该研究报道了一种新型电子探针计算机(EPC60)在解决NP完全问题方面取得的重大突破。该系统采用混合串并行计算模型，通过7种探针算子实现大规模并行计算。在2000顶点图的三着色问题测试中，EPC60以100%准确率完胜主流算法Gurobi(仅6%)，并将计算时间从15天缩短至54 s。该系统具有高度可扩展性，为供应链、金融、通信等领域的复杂优化问题提供了通用解决方案。Abstract:
This study presents a breakthrough in addressing NP-complete problems using a newly developed Electronic Probe Computer (EPC60). The system employs a hybrid serial–parallel computational model and performs large-scale parallel operations through seven probe operators. In benchmark tests on 3-coloring problems in graphs with 2,000 vertices, EPC60 achieves 100% accuracy, outperforming the mainstream solver Gurobi, which succeeds in only 6% of cases. Computation time is reduced from 15 days to 54 seconds. The system demonstrates high scalability and offers a general-purpose solution for complex optimization problems in areas such as supply chain management, finance, and telecommunications. Objective NP-complete problems pose a fundamental challenge in computer science. As problem size increases, the required computational effort grows exponentially, making it infeasible for traditional electronic computers to provide timely solutions. Alternative computational models have been proposed, with biological approaches—particularly DNA computing—demonstrating notable theoretical advances. However, DNA computing systems continue to face major limitations in practical implementation. Methods Computational Model: EPC is based on a non-Turing computational model in which data are multidimensional and processed in parallel. Its database comprises four types of graphs, and the probe library includes seven operators, each designed for specific graph operations. By executing parallel probe operations, EPC efficiently addresses NP-complete problems.Structural Features:EPC consists of four subsystems: a conversion system, input system, computation system, and output system. The conversion system transforms the target problem into a graph coloring problem; the input system allocates tasks to the computation system; the computation system performs parallel operations via probe computation cards; and the output system maps the solution back to the original problem format.EPC60 features a three-tier hierarchical hardware architecture comprising a control layer, optical routing layer, and probe computation layer. The control layer manages data conversion, format transformation, and task scheduling. The optical routing layer supports high-throughput data transmission, while the probe computation layer conducts large-scale parallel operations using probe computation cards. Results and Discussions EPC60 successfully solved 100 instances of the 3-coloring problem for graphs with 2,000 vertices, achieving a 100% success rate. In comparison, the mainstream solver Gurobi succeeded in only 6% of cases. Additionally, EPC60 rapidly solved two 3-coloring problems for graphs with 1,500 and 2,000 vertices, which Gurobi failed to resolve after 15 days of continuous computation on a high-performance workstation.Using an open-source dataset, we identified 1,000 3-colorable graphs with 1,000 vertices and 100 3-colorable graphs with 2,000 vertices. These correspond to theoretical complexities of O(1.3289n) for both cases. The test results are summarized in Table 1.Currently, EPC60 can directly solve 3-coloring problems for graphs with up to n vertices, with theoretical complexity of at least O(1.3289n).On April 15, 2023, a scientific and technological achievement appraisal meeting organized by the Chinese Institute of Electronics was held at Beijing Technology and Business University. A panel of ten senior experts conducted a comprehensive technical evaluation and Q&A session. The committee reached the following unanimous conclusions:1. The probe computer represents an original breakthrough in computational models.2. The system architecture design demonstrates significant innovation.3. The technical complexity reaches internationally leading levels.4. It provides a novel approach to solving NP-complete problems.Experts at the appraisal meeting stated, “This is a major breakthrough in computational science achieved by our country, with not only theoretical value but also broad application prospects.” In cybersecurity, EPC60 has also demonstrated remarkable potential. Supported by the National Key R&D Program of China (2019YFA0706400), Professor Xu Jin’s team developed an automated binary vulnerability mining system based on a function call graph model. Evaluation of the system using the Modbus Slave software showed over 95% vulnerability coverage, far exceeding the 75 vulnerabilities detected by conventional depth-first search algorithms. The system also discovered a previously unknown flaw, the “Unauthorized Access Vulnerability in Changyuan Shenrui PRS-7910 Data Gateway” (CNVD-2020-31406), highlighting EPC60’s efficacy in cybersecurity applications.The high efficiency of EPC60 derives from its unique computational model and hardware architecture. Given that all NP-complete problems can be polynomially reduced to one another, EPC60 provides a general-purpose solution framework. It is therefore expected to be applicable in a wide range of domains, including supply chain management, financial services, telecommunications, energy, and manufacturing. Conclusions The successful development of EPC offers a novel approach to solving NP-complete problems. As technological capabilities continue to evolve, EPC is expected to demonstrate strong computational performance across a broader range of application domains. Its distinctive computational model and hardware architecture also provide important insights for the design of next-generation computing systems. -
表 1 性能实测(对比AMD Ryzen™ 99950X工作站)
测试集规模 EPC60用时(s) 传统求解器用时(s) 成功率对比 2000顶点×100图 3 430 ≥43 571 100% vs 5.6% 1000 顶点×1000 图4 154 ≥6 1374 98.2% vs 54.3% 
下载: 导出CSV
-
[1] HOCHBA D S. Approximation algorithms for NP-hard problems[J]. ACM SIGACT News, 1997, 28(2): 40–52. doi: 10.1145/261342.571216. [2] ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science, 1994, 266(5187): 1021–1024. doi: 10.1126/science.7973651. [3] XU Jin. Biological Computing[M]. Singapore: Springer, 2025. doi: 10.1007/978-981-96-3870-3. [4] XU Jin. Probe machine[J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(7): 1405–1416. doi: 10.1109/TNNLS.2016.2555845. [5] https://github.com/TCSlabData/3-Coloring-Instances. git. [6] BEIGEL R and EPPSTEIN D. 3-coloring in time O (1.3289n)[J]. Journal of Algorithms, 2005, 54(2): 168–204. doi: 10.1016/j.jalgor.2004.06.008. [7] COOK S A. The complexity of theorem-proving procedures[C]. Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, USA, 1971: 151–158. doi: 10.1145/800157.805047. -
表(1)
计量
- 文章访问数: 222
- HTML全文浏览量: 34
- PDF下载量: 61
- 被引次数: 0
下载:
