A special machine for solving NP-complete problems
KeAi Communications Co., Ltd.Peer-Reviewed Publication
This study presents a specialized Electronic Probe Computer (EPC60) designed to efficiently address NP-complete problems—computational challenges that become increasingly complex as their size grows. The EPC60 system, constructed with 60 fully customized FPGA-based probe computing cards, utilizes a hybrid serial-parallel computational model along with seven fully parallel probe operators. In tests conducted on large-scale 3-coloring problems, the EPC60 achieved 100% accuracy on 2000-vertex graphs in under one hour, significantly surpassing the state-of-the-art solver Gurobi, which attained only 6% accuracy. Given the theoretical mutual reducibility of NP-complete problems in polynomial time, the EPC60 emerges as a universal solver for this class of problems. Additionally, the system's modular design facilitates scalable expansion, presenting a promising hardware solution for addressing real-world optimization challenges in logistics, telecommunications, and manufacturing.
- Journal
- Fundamental Research
- Funder
- National Major Research Instrument Development Project, Key Program of the National Natural Science Foundation of China, General Program of the National Natural Science Foundation of China