NP-complete problems, including optimal routing, scheduling and network design, are foundational to essential tasks across various industries. However, they actually pose challenges for conventional electronic computers.
As the magnitude of these problems grows, the time required to find solutions also increase exponentially, restricting the range of feasible computations. Notably, modern electronic computers face difficulties with these problems due to two primary constraints: physical limitations, as silicon chips near atomic scales and quantum effects begin to interfere with their functionality; and architectural limitations inherent in the Turing machine model, which processes data in a linear and sequential manner.
To that end, a recent study led by Professor Jin Xu at Peking University introduced a non-Turing computational model called the Probe Machine, which has been realized in hardware as the Electronic Probe Computer (EPC60). This innovative approach aims to overcome the fundamental limitations of classical architectures, enhancing both accuracy and efficiency in tackling NP-complete problems.
The team published their results in the KeAi journal Fundamental Research .
“Electronic computers are inherently restricted by the Turing model's linear data arrangement and sequential operations, which render large-scale parallel processing impractical for NP problems,” explains Xu. “Our probe machine organizes data into multidimensional units and employs fully parallel probe operators, allowing for the simultaneous exploration of solution paths without delays between operators.”
The three main findings in the study are:
“In performance benchmarks, EPC60 solved 3-coloring problems on 2,000-vertex graphs with 100% accuracy in 3,430 seconds, while Gurobi—a leading commercial solver—achieved only 5–6% accuracy after 43,571 seconds.,” shares Xu. “A particularly challenging instance that stumped Gurobi even after 15 days of computation — EPC60 managed to find valid colorings in under one minute.”
The team highlighted that their findings have moved from this particular topic from a theoretical nature to a that of a deployable machine—one that not only outperforms the best software solvers, but is also inherently scalable. “This marks a turning point in computational intelligence, offering a universal, hardware-based solver for complex problems ranging from supply chain logistics to circuit design,” adds Xu.
The team plans to scale the EPC architecture further and explore its integration into high-performance computing environments for real-time industrial applications.
###
Contact the author: Jin Xu, School of Computer Science, Peking University, Beijing 100871, China, jxu@pku.edu.cn
The publisher KeAi was established by Elsevier and China Science Publishing & Media Ltd to unfold quality research globally. In 2013, our focus shifted to open access publishing. We now proudly publish more than 200 world-class, open access, English language journals, spanning all scientific disciplines. Many of these are titles we publish in partnership with prestigious societies and academic institutions, such as the National Natural Science Foundation of China (NSFC).
Fundamental Research
Computational simulation/modeling
People
A special machine for solving NP-complete problems.
The authors declare that they have no conflicts of interest in this work.